BOJ G4 2665 미로만들기 JAVA

2665번: 미로만들기

---

문제 읽기

일단 맵이 0 또는 1로 이루어져 있고, 흰 방만 지나갈 수 있으며, 검은 방을 바꾸는 것을 최소로 해야 한다. 이런 문제는 0-1 BFS로 바로 해결할 수 있다.

 

0-1 BFS에 대한 설명은 다음에서 볼 수 있다.

0-1 BFS

---

문제 풀기

해당 문제는 검은 방이 0이고 흰 방이 1이라는 사실만 주의하면, 0-1 BFS를 쓰면 바로 풀리는 문제이다.

 

보통은 이런 문제에서 마음대로 지나갈 수 있는 흰 방이 0이고 막혀있는 검은 방이 1이라서, 1을 ‘비용’으로 보고 0-1 BFS를 적용한다. 하지만 이건 반대라서, 나는 그냥 입력 받을 때 +1%2로 0과 1을 바꿔줬다.

 

그 외에는 0-1 BFS 알고리즘과 동일하다.

필요한 것

• deque
• dist

---

코드

package ps.ㄱSolving;

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

public class BOJ_G4_2665_미로만들기 {
    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static int N;
    static int[][] map;
    static int[][] dist;
    static int INF = Integer.MAX_VALUE - 50 * 50;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(in.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++){
            String[] split = in.readLine().split("");
            for (int j = 0; j < N; j++){
                map[i][j] = (Integer.parseInt(split[j]) + 1) % 2;
            }
        }

        dist = new int[N][N];
        for (int i = 0; i < N; i++){
            Arrays.fill(dist[i], INF);
        }
        zeroOneBfs(new Pos(0, 0));

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

    private static void zeroOneBfs(Pos pos) {
        //dist, dec
        Deque<Pos> dec = new ArrayDeque<>();
        dec.offer(pos);
        dist[pos.r][pos.c] = 0;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = { 0, 0, -1, 1};

        while(!dec.isEmpty()){
            Pos front = dec.pollFirst();

            for (int di = 0; di < 4; di++){
                int nr = front.r + dr[di];
                int nc = front.c + dc[di];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

                if (dist[nr][nc] > dist[front.r][front.c] + map[nr][nc]){
                    dist[nr][nc] = dist[front.r][front.c] + map[nr][nc];
                    if (map[nr][nc] == 0) dec.addFirst(new Pos(nr, nc));
                    else dec.addLast(new Pos(nr, nc));
                }
            }
        }
    }
}