[백준 9376] 탈옥 -JAVA // le_effort//

여지껏 푼 bfs 문제중에 제일 어려웠던것 같다...

 

맨 처음 틀린 접근 방법: 문의 개수를 카운트 하고 dfs에서 문의 개수에 도달하면 하는 방법으로 했었는데

맵이 100,100 으로 커지면 정말 말도 안되는 연산시간을 요구하기 때문에 하면 안됨으로 실패했다

dfs할 땐 문이 8개면

if(level == 8) return 하는 식으로 접근 했었고

map[x][y]='.' (문에서 빈칸으로 바꿔줌)

dfs(level+1)

map[x][y] = '#' 

 

dfs(level+1) // 문을 안바꿔줌

 

이런식으로 했었는데 틀린 접근이였다

 

결국 어떻게 풀어야 할 지 몰라서 다른 블로그를 참고했는데 정말 어려웠다

나는 이런식의 문제는 맵을 바꾸는 방법(문을 빈칸으로 바꾸고 안되면 빈칸으로 바꾼걸 다시 문으로 바꿈 ) 으로만 접근했었는데 그런 방법으로 접근하지 않는 방법을 이 문제를 통해 배운 것 같아  좋은 문제라고 생각한다.

이 문제는 문이 있으면 이동거리에 +1 을 하고 문이 아니면 그 전 단계의 값을 그대로 받는 것 이다

 

 

다른 블로그를 통해 보니 이 문제의 접근방법은

1. 외부자(상근)이가 죄수 1 죄수 2를 꺼내는 방법

2. 죄수1이 죄수2와 만나 나가는 방법

3. 죄수2가 죄수1을 만나 나가는 방법인데

 

각각의 거리를 구한 다음에 다 더한 후 최소값을 구하는 건데 자세한건 코드를 보며 설명하겠다.

 

 

boolean flag = false;    //죄수가 두명이 있는데 둘다 각각의 큐에 넣어주기 위해 flag를 둠
            for(int i=0; i<h+2; i++) {
                for(int j=0; j<w+2; j++) {
                    map[i][j]='.';
                }
            }
            for(int i=1; i<=h;i ++) {
                String str = br.readLine();
                for(int j=1; j<=w; j++) {
                    map[i][j] = str.charAt(j-1);
                    if(!flag && map[i][j] == '$') {    // 첫번째 덱에넣어줌
                        person1.add(new Node(i,j));
                        flag =  true;    // 이것을 통해 첫째죄수와 둘째죄수를 구분해 큐에 넣을수 있다.
                    }
                    else if(flag && map[i][j] == '$') {
                        person2.add(new Node(i,j));    // 두번째 덱에 넣어줌
                    }
                }
            }

만약 기존의 맵이 3x3인 경우 상근이가 감옥의 위,아래,오른쪽,왼쪽 어디서든 접근 하기 위해선

세번째 그림인 5x5 맵이 되어야 한다 . 

맵의 크기가 n일경우 [n+1][n+1] 만 하면 되는거 아닌가? 라고 생각 할 수도 있는데 그렇게 하면

두번째 그림처럼 된다.

 

여기서 맵을 확장 할 수 있는 이유는 우리는 위에서도 언급말한 것 처럼 '벽' 일 경우에만 이동거리 +1 을 해 줄 것이다.

즉 새로 추가한 부분은 이 문제 기준으로 '.' 으로 초기화를 하여 이동거리에는 아무런 영향을 미치지 않는다

나도 왜 맵을 확장하는지 이해하기가 너무 힘들었는데 출구가 어디서든 있을 수 있으니 기존의 맵에서 상하좌우 어느 방향으로던 검사를 해야한다고 생각했다.

 

 이 문제에서는 덱을 이용했는데 이는 코드를 보며 이해 해보도록 하겠다.

 

public static int [][] bfs(Deque<Node> q) {
        int dist[][] = new int[h+2][w+2];
        visited = new boolean[h+2][w+2];
        while(!q.isEmpty()) {
            Node o = q.remove();
            visited[o.x][o.y]= true;
            for(int i=0; i<4; i++) {
                int nx = o.x+dx[i];
                int ny = o.y+dy[i];
                if(nx>=0 && nx<h+2 && ny>=0 && ny<w+2) {
                    if(map[nx][ny]=='*') {
                        continue;
                    }
                    if(!visited[nx][ny]) {
                        if(map[nx][ny]=='#') {        // 문 이라면 1 추가
                            dist[nx][ny]=dist[o.x][o.y]+1;
                            visited[nx][ny] = true;
                            q.addLast(new Node(nx,ny));
                        }
                        else {    //문이 아니면 기존의 값을 가지고 간다
                            visited[nx][ny]= true;
                            dist[nx][ny] = dist[o.x][o.y];
                            q.addFirst(new Node(nx,ny));
                        }
                    }
                }
            }
        }
        return dist;
    }

bfs 함수는 이렇게 생겼다

11-13번째 줄은 '*'이면 지나 갈 수 없는 부분이니 고려를 해주지 않았다.

그후 기존 bfs와 좀 다른게 15-24번째줄 라인인데

덱을 사용했다

문을 지나 갈 경우 덱의 뒤쪽에 넣어줬다

이유는 최단거리를 구해야하기 때문이다

이 조건에서 한 번 방문한 visited[nx][ny]는 또 방문하지 않음으로

 

예를들어 거리가 0 인 좌표가 상하좌우를 통해 nx,ny를 가는경우와

기존 거리가 1인 좌표가 상하좌우를 통해 nx,ny를 가는 경우가 있기 때문에

거리+1 을 하면 뒤쪽으로 넣어주어 최단 거리를 위한 거리가 0인 것을 큐에서 빼주면 된다.

 

그 후 각각의 케이스 (외부자, 죄수1, 죄수2) bfs를 해 이동 거리를 다 구한 다음에

 한꺼번에 더해주고 최소값을 찾으면 된다 이 과정에서도 지나 갈 수 없는 '*' 은 스킵한다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int t,h,w;
    static int ans = Integer.MAX_VALUE;
    static Character map[][];
    static boolean visited[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static Deque<Node>s = new ArrayDeque<>(); // 상근이
    static Deque<Node>person1 = new ArrayDeque<>();    // 죄수1
    static Deque<Node>person2 = new ArrayDeque<>();    //죄수2
    static int fin_dist[][];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        while(t-- >0) {
            ans = Integer.MAX_VALUE;
            s.clear();
            person1.clear();
            person2.clear();
            
            String[] tt = br.readLine().split(" ");
            h = Integer.parseInt(tt[0]);
            w = Integer.parseInt(tt[1]);
            map =  new Character[h+2][w+2];
            fin_dist = new int[h+2][w+2];
            boolean flag = false;    //죄수가 두명이 있는데 둘다 각각의 큐에 넣어주기 위해 flag를 둠
            for(int i=0; i<h+2; i++) {
                for(int j=0; j<w+2; j++) {
                    map[i][j]='.';
                }
            }
            for(int i=1; i<=h;i ++) {
                String str = br.readLine();
                for(int j=1; j<=w; j++) {
                    map[i][j] = str.charAt(j-1);
                    if(!flag && map[i][j] == '$') {    // 첫번째 큐에넣어줌
                        person1.add(new Node(i,j));
                        flag =  true;    // 이것을 통해 첫째죄수와 둘째죄수를 구분해 큐에 넣을수 있다.
                    }
                    else if(flag && map[i][j] == '$') {
                        person2.add(new Node(i,j));    // 두번째 큐에 넣어줌
                    }
                }
            }
            
            s.add(new Node(0,0));
            int temp[][] = bfs(s);
            int temp1[][] = bfs(person1);
            int temp2[][] = bfs(person2);
            for(int i=0; i<h+2; i++) {
                for(int j=0; j<w+2; j++) {
                    fin_dist[i][j] = temp[i][j]+temp1[i][j]+temp2[i][j];
                }
            }
            for(int i=0; i<h+2; i++) {
                for(int j=0; j<w+2; j++) {
                    if(map[i][j]=='*') {
                        continue;    // 벽은 못가니 고려 x
                    }
                    if(map[i][j]=='#') {
                        fin_dist[i][j]-=2;
                    }
                    ans = Math.min(ans, fin_dist[i][j]);
                }
            }
            System.out.println(ans);
        }
    }
    public static int [][] bfs(Deque<Node> q) {
        int dist[][] = new int[h+2][w+2];
        visited = new boolean[h+2][w+2];
        while(!q.isEmpty()) {
            Node o = q.remove();
            visited[o.x][o.y]= true;
            for(int i=0; i<4; i++) {
                int nx = o.x+dx[i];
                int ny = o.y+dy[i];
                if(nx>=0 && nx<h+2 && ny>=0 && ny<w+2) {
                    if(map[nx][ny]=='*') {
                        continue;
                    }
                    if(!visited[nx][ny]) {
                        if(map[nx][ny]=='#') {        // 문 이라면 1 추가
                            dist[nx][ny]=dist[o.x][o.y]+1;
                            visited[nx][ny] = true;
                            q.addLast(new Node(nx,ny));
                        }
                        else {    //문이 아니면 기존의 값을 가지고 간다
                            visited[nx][ny]= true;
                            dist[nx][ny] = dist[o.x][o.y];
                            q.addFirst(new Node(nx,ny));
                        }
                    }
                }
            }
        }
        return dist;
    }
}
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}