[DFS] 목수의 미로 탈출

문제

입출력

💡 사고의 흐름

• 1을 최대 1개까지 깰 수 있다라는 말의 의미를 다르게 생각해본다면 쉽게 해결할 수 있는 문제였다.
• 시작점에서 1까지, 도착점에서 1까지의 거리를 각각 구해서 더한다면, 1을 하나 거쳐갈 수 있는 경로의 길이가 나온다. -> 이 부분을 생각하는 것이 힘들었다(힌트로 해결함)
• 따라서, 이때 distanceA, distanceB 각각 배열을 구해서 1까지의 거리를 기록한다
• dfs를 각각 돌린 다음, distanceA+distanceB의 최솟값을 찾아준다.

Code

import sys
from collections import deque

n,m = map(int, sys.stdin.readline().split())
maze = []
distanceA = [[0 for _ in range(1010)] for _ in range(1010)]
distanceB = [[0 for _ in range(1010)] for _ in range(1010)]
check =[[False for _ in range(1010)] for _ in range(1010)]

for i in range(n):
  maze.append(list(map(int, sys.stdin.readline().split())))

def bfs(a,b,distance):
  q = deque()
  q.append((a,b))
  check[a][b] = True
  dx=[0,0,-1,1]
  dy=[1,-1,0,0]

  while q:
    x,y=q.popleft()
    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      if 0<=nx<n and 0<=ny<m and check[nx][ny]==False:
        distance[nx][ny]  = distance[x][y] +1
        check[nx][ny]=True
        if maze[nx][ny] == 0:
          q.append((nx,ny))

bfs(n-1,0,distanceA)
check =[[0 for _ in range(1010)] for _ in range(1010)]
bfs(0,m-1,distanceB)

result = 1000010
for i in range(n):
  for j in range(m):
    if maze[i][j] >0 and distanceB[i][j]>0 and distanceA[i][j]>0:
      result = min(result, distanceA[i][j]+distanceB[i][j])
print(result)