[백준] 2178- 미로 탐색 문제 풀이(자바,Java)

문제

2178번: 미로 탐색

들어가며

전형적인 bfs 문제라고 할 수 있다.

다만, 아직 bfs로 최단 거리 구하는 것이 익숙하지 않아 이 글을 쓰게 되었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

//11:30
public class 미로_탐색_2178 {
    private static int[][] graph;
    private static int n, m;
    private static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = s[0];
        m = s[1];
        graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            char[] array = br.readLine().toCharArray();
            for (int j = 0; j < array.length; j++) {
                graph[i][j] = Integer.parseInt(String.valueOf(array[j]));
            }
        }
        System.out.println(bfs());
    }

    private static int bfs() {
        Deque<Position> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];

        visited[0][0] = true;
        queue.add(new Position(0, 0,1));
        while (!queue.isEmpty()) {
            Position poll = queue.poll();
            if (poll.x == n - 1 && poll.y == m - 1) {
                return poll.current_distance;
            }
            for (int i = 0; i < 4; i++) {
                int nextX = poll.x + dir[i][0];
                int nextY = poll.y + dir[i][1];
                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m
                        || visited[nextX][nextY] || graph[nextX][nextY] == 0) {
                    continue;
                }
                visited[nextX][nextY] = true;
                queue.add(new Position(nextX, nextY, poll.current_distance+1));

            }
        }
        return -1;
    }

    private static class Position {
        int x;
        int y;
        int current_distance;

        public Position(int x, int y, int current_distance) {
            this.x = x;
            this.y = y;
            this.current_distance = current_distance;
        }
    }
}

풀이

bfs는 필연적으로 탐색 경로가 최단 거리가 된다.

(가중치가 없는 경우)

왜 그런걸까?

 

이는 당연하게도 bfs의 특징에서 기인하는 것인데, 시작 노드에서 가까운 노드부터 탐색한다. 즉, 특정 노드를 처음 방문했을 때, 그 노드까지의 경로는 항상 가장 적은 간선을 사용한 경로이다.

추가로 이미 방문한 노드 또한 탐색하지 않으므로 최단 거리가 보장된다.

 

bfs가 최단 거리 구할 수 있는 건 알겠는데 어떻게 구할 수 있을까??

아까 그 아이디어를 그대로 가져간다.

특정 노드에 처음 방문했을 때, 그 거리는 최단 거리이다.

그러면 위치를 나타내는 배열에 그 값을 저장하면 그만이다.

그러면 시작점에서 그 위치까지의 거리가 저장된다.

이를 갱신하면서 앞으로 나가면?? 우리가 구하고자 하는 목표에 도달하게 된다.

이미 방문한 노드를 탐색하지 않기에 가능한 일이다.

 

이를 구현하는데 대표적으로 두 가지 방식이 있다.

 

1, 따로 거리를 저장할 2차원 배열 만들기

2. 큐에 거리 정보를 담아 넣기

 

상황에 맞춰 하면 된다.

1번의 경우엔 주로 한 점에서 모든 경로가 필요한 경우 사용하고, 2번은 목표지점까지의 거리만 있으면 될 경우에 사용한다.

이 문제에선 2번의 경우로 풀었다.

각각 예시를 보여주면 다음과 같다.

 

1번

초기화 시

int[][] distance = new int[n][m];
distance[startX][startY] = 1; // 시작점은 거리 1

이동 시

distance[nextX][nextY] = distance[currentX][currentY] + 1;

 

2번

초기화 시

class Node {
    int x, y, distance;
    Node(int x, int y, int distance) {
        this.x = x;
        this.y = y;
        this.distance = distance;
    }
}

이동 시

queue.add(new Node(nextX, nextY, current.distance + 1));

 

 

이제 원래 문제로 돌아와보자.

이 문젠 2번 방식으로 사용하여 간단하게? 풀 수 있다.

    private static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

방향 전환에 필요한 2차원 배열이다. 각 배열의 첫 번째 값은 x 두 번째 값은 y이다.

    private static int bfs() {
        Deque<Position> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];

        visited[0][0] = true;
        queue.add(new Position(0, 0,1));
        while (!queue.isEmpty()) {
            Position poll = queue.poll();
            if (poll.x == n - 1 && poll.y == m - 1) {
                return poll.current_distance;
            }
            for (int i = 0; i < 4; i++) {
                int nextX = poll.x + dir[i][0];
                int nextY = poll.y + dir[i][1];
                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m
                        || visited[nextX][nextY] || graph[nextX][nextY] == 0) {
                    continue;
                }
                visited[nextX][nextY] = true;
                queue.add(new Position(nextX, nextY, poll.current_distance+1));

            }
        }
        return -1;
    }

    private static class Position {
        int x;
        int y;
        int current_distance;

        public Position(int x, int y, int current_distance) {
            this.x = x;
            this.y = y;
            this.current_distance = current_distance;
        }
    }

 

클래스를 만들어 값을 계속 갱신한다.

그러다가 끝에 도달하면 여태 계산하던 거리 값을 표시하면 그만이다.