백준 3055 탈출 JAVA

solved.ac = 골드 4

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

3055번: 탈출

 

1. 접근

 

배열의 최대 크기는 50으로 50 * 50칸을 두 번만 방문하면 되니 약 2,500번만에 풀 수 있는 문제다!

 

문제의 조건을 살펴보자면 땅은 . * X D S로 총 다섯개로 나눌 수 있으며

물과 고슴도치는 매번 위, 오른쪽, 아래, 왼쪽 총 네 방향으로 이동이 가능하며 물은 벽과 비버굴을 통과할 수 없고 비버는 벽과 물 웅덩이를 통과할 수 없다.

도망쳐 도치야!!!

다음과 같은 배치가 있다고 가정했을 때 최단 거리는 화살표와 같지만

물은 매 분마다 상,하,좌,우 네 방향으로 퍼져나갈 것이기 때문에 가는길이 막혀버리니

다음과 같이 고슴도치가 이동했을 때의 거리에 물이 차오르는지 확인하며 지나가야 한다.

즉, 첫 번째 BFS를 통해 물이 차오르는 distance를 저장해주고 두 번째 BFS를 통해 물이 차오르기 전에 지나갈 수 있는지 확인하며 distance를 저장한 후 목적지의 값을 출력해주면 된다.

 

2. 풀이

 

변수 세팅

static int R, C;
static String[] A;
static int[][] waterDist, hedgeDist;
static int[][] dir = {{-1, 0}, {0 , 1}, {1, 0}, {0, -1}}; // 물이 갈 수 있는 방향
public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());
    R = Integer.parseInt(st.nextToken());
    C = Integer.parseInt(st.nextToken());
    waterDist = new int[R][C]; // 물이 차오르는 거리
    hedgeDist = new int[R][C]; // 고슴도치 이동거리
    A = new String[R];
    for (int i = 0; i < R; i++) A[i] = br.readLine();
    solution();
}

 

정답 출력

static void solution() {
    int answer = 0;
    bfsWater(); // 물을 먼저 채워보자!
    bfsHedgehog(); // 물을 피해 가보자!
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i].charAt(j) == 'D') answer = hedgeDist[i][j];
        }
    }
    System.out.println((answer == -1) ? "KAKTUS" : answer); // 모두 통과할 수 없으면 KAKTUS를 출력한다!
}

 

물의 이동거리 BFS

static void bfsWater() {
    Queue<Integer> Q = new LinkedList<>();
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i].charAt(j) == '*') { // 물의 위치를 큐에 담아두자! (BFS 시작점)
                waterDist[i][j] = 0; // 방문했다 치자!
                Q.add(i);
                Q.add(j);
            } else waterDist[i][j] = -1;
        }
    }

    while(!Q.isEmpty()) {
        int x = Q.poll();
        int y = Q.poll();

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue; // 배열범위 초과
            if (A[nx].charAt(ny) != '.') continue; // 물은 벽과 굴을 뚫을 수 없다!
            if (waterDist[nx][ny] != -1) continue; // 이미 방문했다
            waterDist[nx][ny] = waterDist[x][y] + 1; // 이동거리 체크
            Q.add(nx);
            Q.add(ny);
        }
    }

}

 

고슴도치 이동거리 BFS

static void bfsHedgehog() {
    Queue<Integer> Q = new LinkedList<>();
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i].charAt(j) == 'S') { // 고슴도치의 위치를 큐에 담아두자! (BFS 시작점)
                hedgeDist[i][j] = 0; // 방문했다 치자!
                Q.add(i);
                Q.add(j);
            } else hedgeDist[i][j] = -1;
        }
    }

    while(!Q.isEmpty()) {
        int x = Q.poll();
        int y = Q.poll();

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue; // 배열범위 초과
            if (A[nx].charAt(ny) == 'X' || A[nx].charAt(ny) == '*') continue; // 고슴도치는 벽과 물 웅덩이를 뚫을 수 없다!
            if (hedgeDist[nx][ny] != -1) continue; // 이미 방문했다
            if (waterDist[nx][ny] != -1 && hedgeDist[x][y] + 1 >= waterDist[nx][ny]) continue; // 고슴도치가 방문하기 전 물이 차오른다!
            hedgeDist[nx][ny] = hedgeDist[x][y] + 1; // 이동거리 체크
            Q.add(nx);
            Q.add(ny);
        }
    }
}

 

3. 전체코드