[BAEKJOON] 9376 탈옥 (Java)

[ 문제 ]

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.

[ 핵심풀이 ]

사실상 아이디어를 찾는데에 시간을 어마무시하게 쓰다가, 결국엔 빌려온 수밖에없었다.

 

다익스트라를 이용해, 키를 적게가진 좌표를 움직인다 하더라도,

열쇠가 필요한 방을 방문했을때, 처리해야될 방도를 찾지 못하였다.

 

핵심은 다음과같다!

1) 열쇠가 필요한 문이있는 방들에 대해, 몇개의 열쇠를 가지고 움직였는지 체크해준다.

2) 움직이는 사람은 상근이와 두 죄수이다.

3) 상근이는 맨처음에 움직일때, 열쇠를 이용하지않고 두 죄수를 탈옥시킬 수 있는지 확인한다.

4) 할수없다면, 각 사람을 기준으로 0개의 열쇠를가지고 시작하여, 맵전체를 움직인다.

5) 열쇠가 필요한 방을 만난다면, 현재까지 사용한 열쇠의 개수를 해당 방에 누적시킨다.

6) 모두다 움직였다면, 모든 열쇠방을 돌며 최소값을 구한다.

7) 최소값은 해당지점에 세명의 사람이 동시에 만날 수 있는곳을 의미한다.

8) 단, 3명이 동시에 한곳을 연것과 같기때문에, 최소값-2가 실질적인 열쇠 사용횟수가 된다.

[ 핵심소스 ]

상근이가 진입하는 방법은 2가지가있다.

1) 맵 전체를 . 으로 둘러싸는방법

for(char item[] : map)
    Arrays.fill(item, '.');
for(int i=1;i<=H;i++) {
    char temp[] = br.readLine().toCharArray();
    for(int j=0;j<W;j++) {
        map[i][j+1] = temp[j];
        if (map[i][j+1] == '$')
            slave.add(new xy(i, j+1));
        if (map[i][j+1] == '#')
            key.add(new xy(i, j+1));
    }
}

2) 맵 끝자락을 확인하여 가능한 입구를 찾는방법.

for(int i=0;i<H;i++) {
    char temp[] = br.readLine().toCharArray();
    for(int j=0;j<W;j++) {
        map[i][j] = temp[j];
        if (map[i][j] == '$')
            slave.add(new xy(i, j));
        if (map[i][j] == '#')
            key.add(new xy(i, j));
        if (i==0||j==0||i==H-1||j==W-1) {
            if (map[i][j] != '*')
                player.add(new xy(i, j));
        }
    }
}

단, 사용방면에서 1) 이 더 편리한것은 사실이다.

 

문을 열면서 탐색할때, 키를 가장 적게 가지고있는 Data부터 탐색을 시작하게끔해야

모든경우, 모든방에 최소의열쇠를 지닌채로 움직일 수 있다.

1) Dijkstra친구인 우선순위 큐를 이용해준다

static class Data implements Comparable<Data>{
    int y, x, key;
    Data(int y, int x, int key) {
        this.y=y;
        this.x=x;
        this.key=key;
    }
    @Override
    public int compareTo(Data o) {
        return this.key - o.key;
    }
}

PriorityQueue<Data>q = new PriorityQueue<>();

[ Java ]

import java.io.*;
import java.util.*;
public class _9376_탈옥 {
    static final int MAX = 105;
    static int H, W;
	
    static int ay[] = {-1,1,0,0};
    static int ax[] = {0,0,-1,1};
	
    static char map[][];
    static int open[][];
    static boolean visit[][];	
    
    static class xy {
        int y, x;
        xy(int y, int x) {
            this.y=y;
            this.x=x;
        }
    }
    static ArrayList<xy>slave=new ArrayList<xy>();
    static ArrayList<xy>key=new ArrayList<xy>();
	
    static class Data implements Comparable<Data>{
        int y, x, key;
        Data(int y, int x, int key) {
            this.y=y;
            this.x=x;
            this.key=key;
        }
        @Override
        public int compareTo(Data o) {
            return this.key - o.key;
        }
    }
    static void init() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc=Integer.parseInt(br.readLine());
        for(int t=1;t<=tc;t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            map = new char[H+2][W+2];
            open = new int[H+2][W+2];
            visit = new boolean[H+2][W+2];
            slave.clear();
            key.clear();
            for(char item[] : map)
                Arrays.fill(item, '.');
            for(int i=1;i<=H;i++) {
                char temp[] = br.readLine().toCharArray();
                for(int j=0;j<W;j++) {
                    map[i][j+1] = temp[j];
                    if (map[i][j+1] == '$')
                        slave.add(new xy(i, j+1));
                    if (map[i][j+1] == '#')
                        key.add(new xy(i, j+1));
                }
            }
            if (Move()) {
                System.out.println(0);
            }
            else {
                openMove(0, 0);
                for(int i=0;i<slave.size();i++)
                    openMove(slave.get(i).y, slave.get(i).x);
                solve();
            }
        }
    }
    static boolean Move() {
        int find=0;
        Queue<xy>q=new LinkedList<>();
        q.add(new xy(0, 0));
        while(!q.isEmpty()) {
            xy out = q.poll();
            if (map[out.y][out.x] =='$') {
                if(find==1)
                    return true;
                find++;
            }
            for(int i=0;i<4;i++) {
                int ny = out.y+ay[i];
                int nx = out.x+ax[i];
                if(!range(ny, nx) && map[ny][nx] != '#' && !visit[ny][nx]) {
                    visit[ny][nx] = true;
                    q.add(new xy(ny, nx));
                }
            }
        }
        return false;
    }
	static void openMove(int y, int x) {
        PriorityQueue<Data>q = new PriorityQueue<>();
        q.add(new Data(y, x, 0));
        for(boolean item[] : visit)
            Arrays.fill(item, false);
        visit[y][x] = true;
        while(!q.isEmpty()) {
            Data out = q.poll();
            for(int i=0;i<4;i++) {
                int ny = out.y+ay[i];
                int nx = out.x+ax[i];
                int nkey = out.key;
                if(!range(ny, nx) && !visit[ny][nx]) {
                    visit[ny][nx] = true;
                    if (map[ny][nx] == '#') {
                        nkey++;
                        open[ny][nx] += nkey;
                    }
                    q.add(new Data(ny, nx, nkey));
                }
            }
        }
    }
    static void solve() {
        int answer = Integer.MAX_VALUE;
        for(xy item : key)
            answer = Math.min(answer, open[item.y][item.x]);
        System.out.println(answer-2);
    }
    static boolean range(int y, int x) {
        return y<0||x<0||y>H+1||x>W+1||map[y][x]=='*';
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        init();
    }
}