1. 문제
https://www.acmicpc.net/problem/2206
2. 풀이 과정
일반 DFS 문제와 다른점은 벽을 부수고 이미 지나간 경우보다 벽을 안 부수고 돌아서 다시 지나갈 때가 더 길지만 이 값도 저장해두어야 한다. 나중에 나온 벽을 부수고 갔을 때가 최단 경로가 될 수 있기 때문이다.
아래는 추가적으로 테스트 케이스를 만든 것이다.
입력 :
6 5
00000
11110
00000
01111
01011
00000
출력:
10
[소스코드]
import sys
from collections import deque
input = sys.stdin.readline
def bfs():
while queue:
x, y, wall= queue.popleft()
if x == N-1 and y == M-1:
return result[N-1][M-1][wall]
for i in range(4):
nx = x + dxy[i][0]
ny = y + dxy[i][1]
if 0<=nx<N and 0<=ny<M:
if graph[nx][ny] == '0' and result[nx][ny][wall] == 0:
result[nx][ny][wall] = result[x][y][wall] + 1
queue.append([nx, ny, wall])
elif graph[nx][ny] == '1'and wall == 0:
result[nx][ny][1] = result[x][y][0]+1
queue.append([nx, ny, 1])
return -1
N, M = map(int, input().split())
graph = [input() for _ in range(N)]
result = [[[0, 0] for _ in range(M)] for _ in range(N)] #벽 안 뚫고 갔을 때, 뚫고 갔을 때
dxy = [(0, -1), (1, 0), (0, 1), (-1, 0)]
queue = deque()
queue.append([0, 0, 0])
result[0][0] = [1, 0]
print(bfs())
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Python_DynamicProgramming] 백준 11727번 : 2xn 타일링 2 (0) | 2021.12.04 |
---|---|
[Python_DFS&BFS] 백준 16236번 : 아기 상어 (0) | 2021.12.01 |
[Python_Greedy] 백준 1339번 : 단어 수학 (0) | 2021.11.08 |
[Python_DynamicProgramming] 백준 1912번 : 연속합 (0) | 2021.11.02 |
[Python_String] 백준 1427번 : 소트인사이드 (0) | 2021.08.22 |