[백준] 2655 - 미로 만들기 문제 풀이(자바,Java)

문제

2665번: 미로만들기

들어가며

우선순위 큐를 생각도 못했다.

소모 시간	1시간
성공 여부	X

두 가지의 풀이를 제시해보고자 한다.

첫 번째는, 우선 순위 큐와 넣는 클래스 안에 코스트를 넣어 만든 방식

두 번째는, 코스트를 따로 배열로 관리하여 이전 값과 비교하는 방식이다.

첫 번째 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

//3:27
public class 미로만들기_2655 {
    private static char[][] graph;
    private static int v;
    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));
        v = Integer.parseInt(br.readLine());
        graph = new char[v][v];
        for (int i = 0; i < v; i++) {
            char[] array = br.readLine().toCharArray();
            graph[i] = array;
        }
        bfs(0, 0);
    }

    private static void bfs(int startX, int startY) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        boolean[][] visited = new boolean[v][v];

        visited[startX][startY] = true;
        queue.add(new Node(startX, startY,  0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.x == v - 1 && node.y == v - 1) {
                System.out.println(node.passCountBlackRoom);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nextX = node.x + dir[i][0];
                int nextY = node.y + dir[i][1];
                if (nextX < 0 || nextY < 0 || nextX >= v || nextY >= v
                        || visited[nextX][nextY]) {
                    continue;
                }
                if (graph[nextX][nextY] == '0') {
                    queue.add(new Node(nextX, nextY, node.passCountBlackRoom + 1));
                } else {
                    queue.add(new Node(nextX, nextY, node.passCountBlackRoom));
                }

                visited[nextX][nextY] = true;
            }
        }
    }

    private static class Node implements Comparable<Node> {
        int x;
        int y;
        int passCountBlackRoom;

        public Node(int x, int y,int passCountBlackRoom) {
            this.x = x;
            this.y = y;
            this.passCountBlackRoom = passCountBlackRoom;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(passCountBlackRoom, o.passCountBlackRoom);
        }
    }
}

풀이

이 문제의 핵심은 다음 경로를 지정할 때, 제일 검은 색 방 지난 수가 적은 경로를 선택하는 것이다.

그걸 바로 우선 순위 큐를 사용하여 풀 수 있다.

추가로 visited 배열을 통해 이전 방문을 체크하여 재방문이 일어나지 않도록 한다.

 

기존 bfs의 방식에서 우선 순위 큐로 바뀐 모습이다.

 

두 번째 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    private static int[][] graph;
    private static int v;
    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));
        v = Integer.parseInt(br.readLine());
        graph = new int[v][v];
        for (int i = 0; i < v; i++) {
            String line = br.readLine();
            for (int j = 0; j < v; j++) {
                graph[i][j] = line.charAt(j) - '0';
            }
        }
        System.out.println(bfs(0, 0));
    }

    private static int bfs(int startX, int startY) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        int[][] cost = new int[v][v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                cost[i][j] = Integer.MAX_VALUE;
            }
        }

        cost[startX][startY] = 0;
        queue.add(new Node(startX, startY, 0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.x == v - 1 && node.y == v - 1) {
                return node.passCountBlackRoom;
            }

            for (int i = 0; i < 4; i++) {
                int nextX = node.x + dir[i][0];
                int nextY = node.y + dir[i][1];

                if (nextX < 0 || nextY < 0 || nextX >= v || nextY >= v) {
                    continue;
                }

                int newCost = node.passCountBlackRoom + (graph[nextX][nextY] == 0 ? 1 : 0);

                if (newCost < cost[nextX][nextY]) {
                    cost[nextX][nextY] = newCost;
                    queue.add(new Node(nextX, nextY, newCost));
                }
            }
        }

        return -1; // 도달 불가능한 경우 (문제 조건상 발생하지 않음)
    }

    private static class Node implements Comparable<Node> {
        int x;
        int y;
        int passCountBlackRoom;

        public Node(int x, int y, int passCountBlackRoom) {
            this.x = x;
            this.y = y;
            this.passCountBlackRoom = passCountBlackRoom;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.passCountBlackRoom, o.passCountBlackRoom);
        }
    }
}

 

풀이

이 방식은 기존 visited 배열을 확장한 버전이다.

결국 우리가 선택해야 하는 건 검은색 방이 적게 통과한 경로이다.

이 말은 적게 선택하는 걸 고르다보면 결국엔 이전 방문했던 경로는 선택하지 않게 된다는 것이다.

        int[][] cost = new int[v][v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                cost[i][j] = Integer.MAX_VALUE;
            }
        }

이를 위해 cost라는 2차원 배열을 만든다.

 

            for (int i = 0; i < 4; i++) {
                int nextX = node.x + dir[i][0];
                int nextY = node.y + dir[i][1];

                if (nextX < 0 || nextY < 0 || nextX >= v || nextY >= v) {
                    continue;
                }

                int newCost = node.passCountBlackRoom + (graph[nextX][nextY] == 0 ? 1 : 0);

                if (newCost < cost[nextX][nextY]) {
                    cost[nextX][nextY] = newCost;
                    queue.add(new Node(nextX, nextY, newCost));
                }
            }

새로운 코스트를 계산 한 뒤 이 값이 다음 가고자 하는 곳의 코스트보다 작다면, 다음 위치로 넘어간다.

(초기화를 int MAX로 했기 때문에, 첫 방문도 포함된다)