[백준 2178번] 미로 탐색

from collections import deque

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

# n x m 크기의 미로
maze = []

# 방문 여부 확인용 2차원 배열
visited = [[False]*m for _ in range(n)]

# 미로 입력받고 저장
for _ in range(n):
    maze.append(list(map(int,input())))

# bfs 함수
def bfs(x,y):

    # 방문 처리
    visited[x][y] = True
    
    # queue 자료구조 선언
    queue = deque([(x,y)])

    while queue:
        v = queue.popleft()

        vx = v[0]
        vy = v[1]
        
        nx = [-1,1,0,0]
        ny = [0,0,-1,1]

        # 상-하-좌-우 탐색
        for i in range(4):

            temp_x = vx + nx[i]
            temp_y = vy + ny[i]
            
            # 배열의 범위를 벗어나는지 확인
            if temp_x >= 0 and temp_x<n and temp_y >= 0 and temp_y <m:

                # 방문했는지 여부 / 이동가능한 칸인지 확인
                if (visited[temp_x][temp_y] == False) and (maze[temp_x][temp_y] != 0) :
                    # 이동 가능하다면 큐에 추가
                    queue.append((temp_x,temp_y))
                    # 방문처리
                    visited[temp_x][temp_y] = True
                    # 한칸 씩 이동할 때마다 이전 값 +1 처리
                    maze[temp_x][temp_y] = maze[vx][vy] + 1

bfs(0,0) # (0,0)부터 시작
print(maze[n-1][m-1]) # 최종 (n,m)값(최소 칸수))

이번 문제는 2차원 배열로 주어지는 미로에서 (0,0)부터 특정 위치로의 최소 이동 칸수(최단 경로)를 구하는 문제이기 때문에, 탐색 알고리즘 중에서도 BFS를 사용해서 풀어야 하는 문제라는 것을 먼저 캐치할 수 있어야 한다 !

 

이전에 다루었던 문제랑 한가지 달랐던 점은 여태까지 다루었던 문제는 정점과 간선의 정보를 입력받아서 그래프의 형태로 탐색했었다면, 이번 문제는 2차원 배열로 된 연결 관계를 BFS를 활용하여 풀어야 한다는 것이다.

따라서 2차원 배열(maze)을 입력받아서 저장하고, 방문여부를 확인하는 리스트(visited)도 2차원 배열로 선언해주었다.

 

그 후 그래프에서는 각 정점과 연결된 정점을 순회해가며 BFS를 했다면, 이 문제에서는 서로 인접한 칸으로만 이동할 수 있기 때문에 상-하-좌-우 순서로 이동하면서 이동가능한 칸을 순회해가며 BFS를 하였다.

 

BFS 알고리즘을 다른 방식으로 활용해보는 좋은 문제였다 😎