[백준] | JAVA, 자바 | 2665번 - 미로만들기

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

---

문제 풀이 :

1. 방의 수 n 입력받기

2. n x n 크기의 바둑판 모양의 정보 입력받기

3-1. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다.

3-2. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다.

3-3. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

3-4. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

4. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성

4-1. 단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    // x,y 좌표와 검은 방을 흰 방으로 변경한 횟수를 가지고 있는 객체 Coordinate
    static class Coordinate{
        int x,y,change;
        public Coordinate(int x, int y, int change) {
            this.x = x;
            this.y = y;
            this.change = change;
        }
    }
    private static int n, cnt, max;
    private static int[][] map;
    private static boolean[][][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 방의 수 n 입력받기
        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        visited = new boolean[n][n][50*50 + 1];

        // 2. n x n 크기의 바둑판 모양의 정보 입력받기
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(line.charAt(j)));
                if(map[i][j] == 0) max++;
            }
        }

        bfs();
        // 4. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성
        System.out.println(cnt);
    }

    private static void bfs() {
        cnt = Integer.MAX_VALUE;
        Queue<Coordinate> queue = new ArrayDeque<>();
        // 3-3. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고,
        visited[0][0][map[0][0]] = true;
        queue.add(new Coordinate(0,0,map[0][0] == 0 ? 1 : 0));

        int[][] delta = {{-1,0},{1,0},{0,-1},{0,1}};

        while (!queue.isEmpty()) {
            Coordinate temp = queue.poll();

            // 3-3. 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.
            if (temp.x == n - 1 && temp.y == n - 1) {
                // 3-4. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다. / bfs 최단거리 탐색
                if (temp.change < cnt) cnt = temp.change;
            }

            for (int i = 0; i < 4; i++) {
                int nr = temp.x + delta[i][0];
                int nc = temp.y + delta[i][1];

                // 3-2. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다.
                // 만약 검은 방을 흰방으로 바꾼 횟수가 저장된 max의 값보다 크다면 더 이상 탐색할 필요 x
                if (isRange(nr, nc) && !visited[nr][nc][temp.change] && temp.change < max) {
                    if (map[nr][nc] == 0) {
                        if (!visited[nr][nc][temp.change + 1]) {
                            queue.add(new Coordinate(nr, nc, temp.change + 1));
                            visited[nr][nc][temp.change + 1] = true;
                        }
                    } else { // 3-1. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다.
                        queue.add(new Coordinate(nr, nc, temp.change));
                        visited[nr][nc][temp.change] = true;
                    }
                }
            }
        }

        // 4-1. 단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답
        if (cnt == Integer.MAX_VALUE) cnt = 0;
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < n && nc >= 0 && nc < n;
    }
}