[알고리즘 / 백준] 2178 - 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

문제는 위와 같으며, 우선순위 큐와 BFS 를 통해 문제를 해결할 수 있습니다.

 

먼저 주어진 미로를 이차원 배열에 저장하고, 출발점(0,0)을 우선순위 큐에 추가합니다. 이때 [현재 위치까지 지나온 위치 수(현재 위치 포함), 현재 위치의 x 값, 현재 위치의 y 값] 형태로 데이터를 저장합니다. 현재 위치까지 지나온 위치 수를 기준으로 우선순위 큐에 데이터를 저장하게 되면 같은 위치를 확인하게 되는 경우 해당 위치까지 방문한 최소 위치 수를 알 수 있습니다.

 

미로 이차원 배열과 함께 미로의 해당 위치를 방문한 적이 있는지를 표시하는 이차원 배열을 추가로 만들어 False 로 초기화 합니다.

 

이후 우선순위 큐에 값이 없을 때까지 반복적으로 위치를 확인하는데, 현재 위치를 큐에서 뽑은 뒤, 이동할 수 있는 상하좌우 위치를 순서대로 확인하면서

1. 다음 위치가 미로 크기 내에 존재하고 2. 다음 위치값이 1로 이동할 수 있는데 아직 방문한 적이 없는 경우

다음 위치를 방문한 것으로 처리하고 우선순위 큐에 다음 위치를 [다음 위치까지 지나온 위치 수(현재 위치까지 지나온 위치 수 + 1), 다음 위치의 x 값, 다음 위치의 y 값] 형태로 저장합니다.

 

최종적으로 현재 위치가 N, M 이 되는 경우 최종 위치에 방문하는데 지나온 최소 노드 수가 저장되어 있으므로 그대로 출력하면 됩니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(x, y):
    queue = []
    heapq.heappush(queue, [1, x, y])  # 출발 위치 우선순위 큐에 저장
    visited[x][y] = True  # 처음 위치 방문 표시

    while queue:
        count, cx, cy = heapq.heappop(queue)  # [현재 위치까지 방문한 노드의 수, 현재 위치 x 값, 현재 위치 y 값]

        if cx == n - 1 and cy == m - 1:  # 최종 위치에 도달한 경우
            return count  # 최종 위치까지 방문한 노드의 수 반환

        for i in range(4):  # 상하좌우 다음 위치를 확인하여
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx < n and 0 <= ny < m:  # 미로 범위 내에 있고
                if maze[nx][ny] == 1 and not visited[nx][ny]:  # 지나갈 수 있는 길이면서 방문한 적이 없는 경우
                    visited[nx][ny] = True  # 다음 위치를 방문한 것으로 처리하고
                    heapq.heappush(queue, [count + 1, nx, ny])  # 우선순위 큐에 [다음 위치까지 방문한 노드의 수, 다음 위치 x 값, 다음 위치 y 값]을 저장


n, m = map(int, stdin.readline().split())
maze = []
for _ in range(n):
    maze.append(list(map(int, stdin.readline().strip())))

visited = [[False] * m for _ in range(n)]
print(bfs(0, 0))

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] maze = new int[n][m];
        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            maze[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
            Arrays.fill(visited[i], false);
        }

        int[][] adj = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  // 아래, 위, 우, 좌 좌표 저장

		// 우선순위 큐 생성 [현재 위치까지 방문한 노드의 수, x 값, y 값] 형태로 데이터를 저장하는데
        // 그중 "현재 위치까지 방문한 노드의 수" 를 기준으로 우선순위 지정
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] t1, int[] t2) {
                return t1[0] - t2[0];
            }
        });
        queue.offer(new int[]{1, 0, 0});  // 시작 지점 우선순위 큐에 저장
        visited[0][0] = true;  // 시작 지점 방문 처리

        while (!queue.isEmpty()) {
            int[] current = queue.poll();  // 현재 위치 정보 뽑기

			// 현재 위치가 도착 지점 위치와 같은 경우
            if (current[1] == n - 1 && current[2] == m - 1) {
                System.out.println(current[0]);  // 도착 지점까지 방문한 노드의 수를 출력하고
                break;  // 종료
            }

			// 주변(상하좌우) 위치를 확인하여
            for (int i = 0; i < 4; i++) {
                int nx = current[1] + adj[i][0];
                int ny = current[2] + adj[i][1];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {  // 다음 위치가 미로 내에 있고
                    if (maze[nx][ny] == 1 && !visited[nx][ny]) {  // 다음 위치로 이동할 수 있으며 아직 이동하지 않은 경우
                        visited[nx][ny] = true;  // 다음 위치를 방문처리
                        queue.offer(new int[]{current[0] + 1, nx, ny});  // 우선순위 큐에 [다음 위치까지 방문한 노드의 수, 다음 위치 x 값, 다음 위치 y 값] 저장
                    }
                }
            }
        }
    }
}