[백준] 2178. 미로 탐색 python

🐳 링크

백준 2178번 미로탐색

🐕 문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

🐾 풀이 방법

1. n,m과 miro를 차례대로 받아준다.
   • 이때, miro에 들어오는 값들은 숫자가 붙어서 들어오므로 str으로 받은 채 list화 하여 이용하는 것이 편하다.
2. (0,0)부터 시작하여 이웃 노드들을 방문한다.
3. 방문할 때, visit 배열의 값에 이전 visit 배열에 저장된 값 + 1을 해준다.

• 이유는, 시간 초과를 해결하기 위해서이다. 다시 제일 처음으로 돌아가는 것이 아닌 이전 값에 +1을 함으로써 최종 (n-1,m-1)에 도달하였을 때 최솟값을 visit 배열에 저장할 수 있다.

solution 코드

1. bfs로 solve한 코드

   import sys
   sys.setrecursionlimit(10**8)
   sys.stdin = open("input.txt","rt")
   

dx = [1,-1,0,0]
dy = [0,0,1,-1]

n,m = [int(x) for x in sys.stdin.readline().split()]
answer = n*m + 1
visit = [[0] * m for _ in range(n)]
visit[0][0] = 1
miro = [list(sys.stdin.readline().strip()) for _ in range(n)]

q = []
q.append((0,0))
while q:
x, y = q.pop(0)
if x == n-1 and y == m-1:
print(visit[x][y])
sys.exit()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if visit[nx][ny] == 0 and miro[nx][ny] == '1':
visit[nx][ny] = visit[x][y] + 1
q.append((nx,ny))

2. dfs로 시간초과 코드
bfs로 문제를 다시 풀어보며 든 생각이, (n,m)까지의 최단 거리를 구하는 문제이므로 dfs처럼 처음부터 (n,m)까지 도달한 뒤 뒤로 빠져나오며 다른 경로를 탐색하는 방법보다는 bfs처럼 이웃 노드들을 모두 탐색하여 visit에 경로 값을 누적한 뒤, 최종 도달했을 때 visit[n-1][m-1]의 값을 출력하는 것이 더 빠르고, 정확한 방법이라는 생각이 들었다. 

```python3
import sys
sys.setrecursionlimit(10**8)
sys.stdin = open("input.txt","rt")

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def dfs(x,y, cnt):
    global answer
    if x == n-1 and y == m-1:
        answer = cnt if answer > cnt else answer
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0 and miro[nx][ny] == '1':
                visit[nx][ny] = 1
                dfs(nx,ny,cnt+1)
                visit[nx][ny] = 0



n,m = [int(x) for x in sys.stdin.readline().split()]
answer = n*m + 1
visit = [[0] * m for _ in range(n)]
visit[0][0] = 1
miro = [list(sys.stdin.readline().strip()) for _ in range(n)]

# miro = [sys.stdin.readline().rstrip() for _ in range(n)]

dfs(0,0,1)
print(answer)