[백준] 2178번 : 미로 탐색 (파이썬)

미로탐색 문제로, dfs나 bfs로 푸는 문제이다. 나는 bfs를 이용하여 문제를 해결하였다.

 

처음 내 코드

from collections import deque

a,b = map(int,input().split())
visit = [[0]*b for _ in range(a)]
for i in range(a):
    c = input()
    for j in range(b):
        visit[i][j] = int(c[j])
print(visit)
#BFS
queue = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]
length=0

for i in range(a):
    for j in range(b):
        if visit[i][j]==1:
            visit[i][j]=0
            queue.append([i,j])
            length+=1
            while queue:
                y,x = queue.popleft()
                for l in range(4):
                    ny=dy[l]+y
                    nx=dx[l]+x
                    if nx>=b or nx<0 or ny>=a or ny<0:
                        continue
                    if not visit[ny][nx]:
                        continue
                    visit[ny][nx]=0
                    queue.append([ny,nx])
                    length+=1
print(length)

 

문제점 : 미로 탐색이므로 최단 거리에 해당하는 칸을 지났을 때만 +1을 해주어야 하는데, 위의 코드에서는 visit=1인 칸을 지나기만 하면 length의 값을 +1해준다. 따라서 위의 코드는 visit=1인 모든 칸의 갯수를 출력한다.

 

문제 해결 후 내 코드 

from collections import deque

a,b = map(int,input().split())
visit = [[0]*b for _ in range(a)]
for i in range(a):
    c = input()
    for j in range(b):
        visit[i][j] = int(c[j])
#BFS
queue = deque()
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(a):
    for j in range(b):
        if visit[i][j]==1:
            queue.append([i,j])
            visit[i][j]+=1
            while queue:
                y,x = queue.popleft()
                for l in range(4):
                    ny=dy[l]+y
                    nx=dx[l]+x
                    if nx>=b or nx<0 or ny>=a or ny<0:
                        continue
                    if visit[ny][nx]!=1:
                        continue
                    visit[ny][nx]=visit[y][x]+1
                    queue.append([ny,nx])
print(visit[a-1][b-1]-1)

 

바뀐점 : 우리는 visit=1인 칸만 지날 것이다. 이미 지난 칸은 다시 지나면 안되므로 visit 값을 바꿔주어야 하는데, 이전 코드에선 visit 값을 1에서 0으로 바꾸어주었다. 반면에 지금 코드에선 이미 지나온 visit=1인 칸의 갯수를 누적해서 더해주며 visit 값을 업데이트 해주었다. 그리고 마지막엔 우리가 구하려는 (N, M)의 위치의 좌표값을 출력해주면 된다. 마지막에 -1을 해준 이유는 우리는 계속 visit=1인 칸을 지나면서 누적합을 해주었는데, 처음에 이 값이 1로 시작했으므로 -1을 해주는 것이다.