[Python] 백준 #2178- 미로 탐색

문제

---

 

2178번: 미로 탐색

코드

---

My answer

import sys
from collections import deque
input= sys.stdin.readline

n,m=map(int,input().split())

graph=[input().rstrip() for _ in range(n)]
visit=[[0]*(m) for _ in range(n)]
direct=[[0,1],[0,-1],[1,0],[-1,0]]

def bfs(x,y):
    Q=deque()
    Q.append((x,y))
    visit[x][y]=1
    while Q:
        x,y=Q.popleft()
        for i in range(4):
            n_x,n_y=x+direct[i][0],y+direct[i][1]
            if(0<=n_x<n and 0<=n_y<m):
                if(visit[n_x][n_y]==0 and graph[n_x][n_y]=='1'):
                    visit[n_x][n_y]=visit[x][y]+1
                    Q.append((n_x,n_y))  
    return 0

bfs(0,0)
#print(visit)
print(visit[n-1][m-1])

 

풀이

---

나는 bfs로 문제를 해결했고, dfs bfs 중 어떤걸 쓸지만 생각하면 구조들이 비슷해서 쉽게 풀 수 있었던 것 같다.

우선 그래프를 입력받고, 방문을 기록하는 visit을 생성한다. 

이후 이전 방문값에 1을 더해주면서 진행해나간다. 예를 들어 2*2격자형태가 있을 때 모두 방문할 수 있는 1칸이라고 생각해보자. [0][0]에서 dfs를 사용하게 되면 direct 즉 상하좌우 이동순서를 내가 정의한거에 따라 방문횟수가 다르게 업데이트 될텐다 예를들어 아래, 오른쪽, 위 이런식의 순서라면 [0][1]이 방문횟수가 3으로 업데이트 될 수도 있다. 그러나 바로 오른쪽이기 때문에 실제로는 0이 맞다. 따라서 bfs를 이용해서 특정지점에서 갈 수 있는 모든 방향에 대해서는 그 특정지점+1을 해주는 방식을 이용한 것이다. ( dfs로는 최단거리가 아닌 가능한 모든경우를 찾을 때만 쓸 수 있을 것 같다. )