백준 2665, 미로 만들기(java)

문제 설명

nxn 모양의 바둑판이 있다. 이때 (0, 0)에서부터 (n-1, n-1)까지 가려고 한다. 다만, 검은 방이 존재하여 갈 수 없을지도 모른다. 때문에 (0, 0)에서부터 (n-1, n-1)까지 갈 수 있으면서 검은 방을 최소한 하얀 방으로 만드는 그 수를 구하여라

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

2665번: 미로만들기

문제 풀이

잘못된 풀이

문제를 본 처음에는 검은 방을 0부터 검은 방의 수 만큼까지 조합으로 만들어서 하얀방을 표시한 다음에 경로를 구해주는 방식을 이용했다. 그러나 메모리 초과가 났다. 최대 50개의 수를 조합으로 만들어서 풀려고 했기 때문인 듯 하다.

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

class Pair {
    int row;
    int col;

    Pair (int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {
    public static int n, blackRoomCount;
    public static int[][] map;
    public static List<Pair> blackRooms;

    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};
    public static boolean finishFlag;
    public static int answer;

    public static void dfs(int count, int target, int index, List<Pair> delete) {

        if (finishFlag) {
            return;
        }

        if (count == target) {
            makeWhiteRoom(true, delete);
            if (bfs()) {
                finishFlag = true;
                answer = count;
                return;
            }
            makeWhiteRoom(false, delete);
        } else {
            for (int i=index; i<blackRoomCount; i++) {
                delete.add(blackRooms.get(i));
                dfs(count+1, target, i+1, delete);
                delete.remove(delete.size()-1);
            }
        }
    }

    public static void makeWhiteRoom(boolean flag, List<Pair> delete) {
        if (flag) {
            // 흰 방으로 만든다.
            for (Pair d : delete) {
                map[d.row][d.col] = 1;
            }
        } else {
            for (Pair d : delete) {
                map[d.row][d.col] = 0;
            }
        }
    }

    public static boolean bfs() {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(0, 0));
        boolean[][] visit = new boolean[n][n];
        visit[0][0] = true;

        while(!queue.isEmpty()) {
            Pair current = queue.poll();
            int cR = current.row;
            int cC = current.col;

            for (int i=0; i<4; i++) {
                int nR = cR + dR[i];
                int nC = cC + dC[i];

                if (nR >= 0 && nR < n && nC >= 0 && nC < n) {
                    if (map[nR][nC] == 1 && !visit[nR][nC]) {
                        visit[nR][nC] = true;
                        queue.add(new Pair(nR, nC));
                    }
                }
            }
        }

        if (visit[n-1][n-1]) {
            return true;
        }

        return false;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        blackRooms = new ArrayList<Pair>();
        finishFlag = false;
        answer = 0;

        for (int i=0; i<n; i++) {
            String[] s = br.readLine().split("");
            for (int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(s[j]);
                if (map[i][j] == 0) {
                    blackRooms.add(new Pair(i, j));
                }
            }
        }

        blackRoomCount = blackRooms.size();
        for (int i=0; i<=blackRoomCount; i++) {
            dfs(0, i, 0, new ArrayList<Pair>());
        }

        System.out.println(answer);

    }

}

올바른 풀이

해당 문제는 bfs로 최단 거리를 움직임과 동시에 다익스트라를 이용해서 풀 수 있다.

 

일단 다익스트라 문제의 풀이는 새로운 노드로 옮겨갈 때 만일 현재 노드가 가지고 있는 값이 새 노드의 값보다 작으면 현재 노드의 값을 새 노드에 옮겨주는 방식을 의미한다. 

 

그렇기에 새로 만든 좌표의 값과 현재의 좌표 값을 비교한다. 여기서 현재의 좌표 값이 더 작아 갱신할 필요가 있다면 새로운 좌표가 검은 방인지 하얀 방인지 확인한다. 여기서 비교하는 값은 지금까지 지워온 검은 방의 최소 수이다.

 

만일 하얀 방이면 그냥 값을 옮기면 된다. 왜냐하면 새로운 좌표에 있는 값이 더 크다는 의미는 과거에 해당 칸까지 갔을 때 검은 방을 더 많이 지워줬다는 의미이기 때문이다. 그렇기에 현재 좌표에서 새로운 좌표로 옮길 때 현재 좌표에 있는 값을 넣어 최소로 지운 검은 방의 수를 넣어준다.

 

만일 검은 방이면 방을 하나 지웠다는 의미로 현재 값에 1을 더한 값을 새로운 좌표에 넣어준다.

 

이렇게 하면 맨 마지막 칸에 있는 값이 최소로 지운 검은 방이 된다.

코드

java

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

class Pair {
    int row;
    int col;

    Pair (int row, int col) {
        this.row = row;
        this.col = col;
    }
}

public class Main {
    public static int n;
    public static int[][] map;

    public static int[] dR = {-1, 0, 1, 0};
    public static int[] dC = {0, 1, 0, -1};

    public static int bfs() {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(0, 0));
        int[][] dist = new int[n][n];

        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }

        dist[0][0] = 0;

        while(!queue.isEmpty()) {
            Pair current = queue.poll();
            int cR = current.row;
            int cC = current.col;

            for (int i=0; i<4; i++) {
                int nR = cR + dR[i];
                int nC = cC + dC[i];

                if (nR >= 0 && nR < n && nC >= 0 && nC < n) {
                    if (dist[nR][nC] > dist[cR][cC]) {
                        if (map[nR][nC] == 1) {
                            dist[nR][nC] = dist[cR][cC];
                        } else {
                            dist[nR][nC] = dist[cR][cC] + 1;
                        }
                        queue.add(new Pair(nR, nC));
                    }
                }
            }
        }

        return dist[n-1][n-1];
    }




    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for (int i=0; i<n; i++) {
            String[] s = br.readLine().split("");
            for (int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }

        System.out.println(bfs());

    }

}