미로찾기 (BFS)- 백준 2178번

출처:

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

2178번: 미로 탐색

 

 위 문제는 기본적인 최단거리 찾기 문제이다. 나는 처음에 DFS로 접근해서 답이 나오지 않았다. 이 문제는 BFS로 풀어야 한다.

import collections

N,M=map(int,input().split())

q=collections.deque()
q.append((0,0))

m=[]
for _ in range(N):
    m.append(list(map(int,input())))
    
arr=[0]*M
visited=[]
for _ in range(N):
    visited.append(arr.copy())
    
visited[0][0]=1

dxy=[(-1,0),(1,0),(0,1),(0,-1)]

 우선 기본적인 문제 세팅을 해준다. 여기서는 dxy 리스트로 현재 위치 지점 m[i][j]에서 상하좌우 좌표 x,y를 구한후 m[x][y]가 1이고(길이 있고) visited[x][y]가 0(방문하지 않았던 지점)이면 visited[x][y]를 visited[i][j]+1 로 값을 바꿔준다.

 

 전체적인 흐름은 현재 위치에서 상하좌우 좌표를 확인하고 그 값들중 조건에 맞는 좌표를 q에 추가한다. 그리고 현재 위치의 상하좌우를 다 확인했으면 q에 추가된 좌표들중 먼저 추가된 순서대로 가서 그 좌표에서 또 상하좌우를 탐색한다.

while q:
    i,j=q.popleft()
    
    for dx,dy in dxy:
        x=i+dx
        y=j+dy
        
        if 0<=x<N and 0<=y<M:
            if m[x][y]==1 and visited[x][y]==0:
                visited[x][y] = visited[i][j] + 1
                q.append((x,y))

 

1) bfs로 풀이시 visited 리스트

2) dfs로 풀이시 visited 리스트