[Baekjoon] 2178. 미로탐색 (DFS/BFS)

문제 바로가기

🔍 코드

from collections import deque

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

maps = []

# nxm 미로 입력받기
for i in range(n):
    maps.append(list(map(int, input())))

#북동남서
dx = [-1, 0, 1, 0] #행
dy = [0, 1, 0, -1] #열


def bfs(a,b):
    q = deque()
    q.append((a,b))

    while q:
        x, y = q.popleft()
        
        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]

            if 0<=tx<=n-1 and 0<=ty<=m-1: #이동했을 때의 위치가 maps의 범위 내에 있는지
                if maps[tx][ty]==1: #이동가능한 길인지, 방문하지 않은 곳인 경우
                    q.append((tx, ty))
                    maps[tx][ty] = maps[x][y] + 1
    
    return maps[n-1][m-1]

print(bfs(0,0))

📌 풀이

이 문제는 BFS를 이용하여 해결할 수 있다. BFS는 시작지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다.

지나는 칸 수를 저장하기 위해 따로 값을 저장할 수도 있지만 maps의 value자체를 이동횟수로 저장하면서 탐색하는 것이 더 효율적이다.

첫 번째 시작 위치는 다시 방문할 수 있도록 되어(maps[0][0]의 값은 1이므로) 다른 값으로 변경될 여지가 있다. 하지만 본 문제에서는 단순히 가장 오른쪽 아래 위치로 이동하는 것을 요구하고 있기 때문에 답을 도출하는 데는 문제가 없다.

💫 배운점

이전에 책에서 같은 문제("미로탈출")를 풀었었는데도 처음에 dfs인줄알고 잘못풀었다...ㅜ dfs와 bfs를 언제 사용해야 유리한지를 몰랐다.
이동할때의 움직임을 리스트(dx, dy)에 담아 for문으로 구현해내는것은 기억했는데 이동하는 최소 칸 수를 카운팅하는건 어떻게 해야 할 지 몰라 결국 정답코드를 참고하였다. (-> 맵 위치값에 카운팅 수를 넣어두는 방법으로 해결)

참고