BOJ#2665 미로 만들기

BOJ#2665 미로 만들기

* 문제

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

Olympiad > 한국정보올림피아드 > KOI 1997 > 고등부 2번

* 풀이

쉬운 문제입니다. 20년 묵은 문제네요, 😅

왜 쉽냐면,

검은 방을 흰색 방으로 바꾸는 개수의 제한도 없고, 바꿀 때 필요한 규칙도 없기 때문입니다.

그냥 이 문제는.. 다익스트라 돌리면 됩니다.

비슷한 문제 : 

1261번 - 알고스팟 https://www.acmicpc.net/problem/1261

2206번 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/431a2fe10059904f604d38bc1375dbc2798db1e1/BOJ%232665_MakeMaze/src/Main.java

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

/**
 * BOJ#2665 미로 만들기
 * https://www.acmicpc.net/problem/2665
 */

public class Main {

    static final int[] dRow = {0, -1, 0, 1};
    static final int[] dCol = {-1, 0, 1, 0};
    static final int BLACK = 0;
    static final int WHITE = 1;
    static final int INF = 1000000000;

    static int n;
    static int[][] map = new int[51][51];
    static int[][] dist = new int[51][51];
    static boolean[][] discovered = new boolean[51][51];

    static {

        for (int i = 0; i < 51; i++) {

            Arrays.fill(dist[i], INF);
        }
    }

    public static void main(String[] args) throws IOException {

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {

            String s = br.readLine();
            for (int j = 0; j < n; j++) {

                map[i][j] = s.charAt(j) - '0';
            }
        }

        // solve
        PriorityQueue<Point> pq = new PriorityQueue<Point>();

        pq.add(new Point(0, 0, 0));
        dist[0][0] = 0;

        while (!pq.isEmpty()) {

            Point u = pq.poll();

            if (u.row == n - 1 && u.col == n - 1) break;

            if (dist[u.row][u.col] < u.dist) continue;

            for (int i = 0; i < 4; i++) {

                int nextRow = u.row + dRow[i];
                int nextCol = u.col + dCol[i];

                if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n) continue;
                if (discovered[nextRow][nextCol]) continue;

                // WHITE
                if (map[nextRow][nextCol] == WHITE) {

                    if (dist[nextRow][nextCol] > dist[u.row][u.col]) {

                        dist[nextRow][nextCol] = dist[u.row][u.col];
                    }
                }
                // BLACK
                else {

                    if (dist[nextRow][nextCol] > dist[u.row][u.col] + 1) {

                        dist[nextRow][nextCol] = dist[u.row][u.col] + 1;
                    }
                }

                pq.add(new Point(nextRow, nextCol, dist[nextRow][nextCol]));
                discovered[nextRow][nextCol] = true;
            }

        } // ~while loop

        System.out.println(dist[n-1][n-1]);
    }
}

class Point implements Comparable<Point> {

    int row, col;
    int dist;

    Point(int row, int col, int dist) {

        this.row = row;
        this.col = col;
        this.dist = dist;
    }

    @Override
    public int compareTo(Point o) {

        return this.dist < o.dist ? -1 : 1;
    }
}