[Algorithm/Java] 백준 2665번 - 미로만들기

---

https://www.acmicpc.net/problem/2665

---

🔍 문제 풀이

알고리즘 선택

다익스트라 vs 0-1 BFS vs BFS

• 다익스트라: 일반 가중치 그래프 최단 경로 -> pq 필요
• 0-1 BFS (Deque BFS): 비용이 0 또는 1일 때 최단 경로 찾기 -> deque로 더 빠르게 처리 가능
• BFS는 단순하게 모든 간선 비용이 동일할 때 사용

💡 Dijkstra를 사용해도 해결 가능하지만, 비용이 0 또는 1일 경우에는 0-1 BFS가 더 효율적이라고 한다.

이 문제는 흰 방(이동 비용 0)과 검은 방(이동 비용 1)이 섞인 가중치가 있는 최단 경로 문제이므로, 다익스트라 또는 0-1 BFS를 사용해야 한다.

• 0-1 BFS:
  • 흰 방으로 이동하는 비용 0인 경로는 Deque의 앞에 넣고, 검은 방으로 이동하는 비용 1인 경로는 Deque의 뒤에 넣어 항상 비용이 낮은 경로를 먼저 탐색하도록 보장
  • Deque를 사용해 BFS처럼 탐색하지만, 비용 0은 앞, 비용 1은 뒤에 넣어 최소 비용 우선 탐색
    • 비용 0(흰방): offerFirst()
    • 비용 1(검은방): offerLast()

• 다익스트라:
  • 우선순위 큐를 사용하여 현재까지 최소 비용인 노드를 선택하고, 인접 노드 비용 갱신
  • 최소 비용 노드부터 선택하며 탐색
  • 모든 간선 가중치가 0 이상이어야 사용 가능

💻 코드

0-1 BFS (Deque BFS)

비용 0 (흰 방)

• 이동해도 비용이 늘지 않으므로, 가장 짧은 경로일 가능성이 높다.
• 따라서 dq.offerFirst()를 사용하여 큐의 맨 앞에 넣어 다음 탐색 순서에서 우선적으로 처리되게 한다.

비용 1 (검은 방)

• 벽을 부숴야 하므로 비용이 1 증가
• 따라서 dq.offerLast()를 사용하여 큐의 맨 뒤에 넣어 비용 0인 노드들이 모두 처리된 다음 순서에 처리되게 한다.

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static int[][] cost; // 흰 방으로 바꾸는 횟수 저장

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int n;

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

        // input
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n][n];
        cost = new int[n][n];

        for(int i=0; i<n; i++){
            Arrays.fill(cost[i], -1);  // 까먹지 말기
        }

        for(int i=0; i<n; i++) {
            String line = br.readLine();
            for(int j=0; j<n; j++){
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        // solve
        int ans = bfs(0, 0);

        // output
        System.out.println(ans);
    }

    static int bfs(int x, int y){
        // 1. 초기화
        Deque<Node> dq = new ArrayDeque<>();

        // 2. 초기값
        dq.offer(new Node(x, y, 0));
        cost[x][y] = 0; // 초기 비용

        // 3. 탐색
        while(!dq.isEmpty()) {
            Node cur = dq.pollFirst();

            // 종료조건
            if(cur.x == n-1 && cur.y == n-1) {
                return cur.cnt;
            }

            // 4방향, 범위
            for(int d = 0; d<4; d++){
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];

                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;


                // 1. 다음 칸의 비용을 먼저 계산
                int nextCnt = cur.cnt + (arr[nx][ny] == 0 ? 1 : 0);


                // 2. 최소 비용 갱신 조건
                // 이미 방문한 곳이라도 더 적은 비용으로
                // 도달할 수 있다면 다시 방문하여 비용을 갱신
                if(cost[nx][ny] == -1 || cost[nx][ny] > nextCnt) {
                    cost[nx][ny] = nextCnt; // 새로운 최소 비용으로 갱신

                    // 가중치에 따라 dq의 앞/뒤에 추가
                    if(arr[nx][ny] == 0) { // 흰 방 (비용 0) -> Deque의 앞에 넣어 우선 처리
                        dq.offerLast(new Node(nx, ny, nextCnt));
                    }
                    else {  // 검은 방 (비용 1) -> Deque의 뒤에 넣어 나중에 처리
                        dq.offerFirst(new Node(nx, ny, nextCnt));
                    }
                }
            }
        }
        return -1;
    }

    static class Node {
        int x, y, cnt;

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

다익스트라

나중에 다익스트라로 구현해볼것

[백준 2665

미로만들기 (BFS, 우선순위 큐)](https://velog.io/@whddn0221/%EB%B0%B1%EC%A4%80-2665-%EB%AF%B8%EB%A1%9C%EB%A7%8C%EB%93%A4%EA%B8%B0-BFS-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90)

스켈레톤 코드 (0-1 BFS)

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static int[][] cost; // 흰 방으로 바꾸는 횟수 저장

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int n;

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

        // input
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n][n];
        cost = new int[n][n];

        for(int i=0; i<n; i++){
            Arrays.fill(cost[i], -1); // 까먹지 말기
        }

        for(int i=0; i<n; i++) {
            String line = br.readLine();
            for(int j=0; j<n; j++){
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        // solve
        int ans = bfs(0, 0);

        // output
        System.out.println(ans);
    }

    static int bfs(int x, int y){


        return -1;
    }

    static class Node {
        int x, y, cnt;

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