[Python_DFS&BFS] 백준 2206번 : 벽 부수고 이동하기

1. 문제

https://www.acmicpc.net/problem/2206

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())