[BOJ 3055] 탈출 (Java, 격자형 그래프 탐색)

 

 

---

문제 링크 

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

3055번: 탈출

---

풀이

- 첫번째 줄에 맵의 크기 R, C 주어짐 (최대 50)

- 비어있는 곳은 '.' / 물이 차있는 지역은 '*' / 돌은 'X' / 비버의 굴은 'D' / 고슴도치의 위치는 'S' 로 표시

- 격자형 그래프 탐색 문제 (상하좌우)

 

- 물 '*'은 매 분마다 비어있는 인접 칸으로 확장

- 물(*)과 고슴도치(S)는 돌을 통과할 수 없음

- 고슴도치(S)는 물(*)이 차있는 구역으로 이동할 수 없음

- 물(*)도 비버의 소굴(D)로 이동할 수 없음 => 물은 매 단계마다 비어있는 곳 채워짐

 

중요*
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.
즉, 다음 시간에 물이 찾을 예정인 칸에 고슴도치는 이동할 수 없다

WATER_TIMING[nx][ny] <= HEGEHOG_DIST[x][y] + 1

 

절차

1) 빈칸(.)에 물이 찰 예정인 시간을 구함 DIST_WATER 구함 (격자형 그래프 탐색) 

2) 고슴도치(S) 시작점을 찾아 해당 위치부터 HEGEHOG_DIST 배열 채우면서 이동 

- 이동하게 될 위치가 물이 차지 않음을 확인해야 하고, 빈 공간(.) 이거나 비버의 굴(D)인 경우 이동

3) 탐색 완료 후 비버의 굴(D) 위치 값이 0이면 KAKTUS, 아니면 값 출력 -- HEGEHOG_DIST배열

 

행운의 고슴도치의 가호가 함께 하길

 

예제 입력 1의 경우 3 출력

i \ j	0	1	2
0	D	.	*
1	.	.	.
2	.	S	.

 

WATER_TIMING

i \ j	0	1	2
0	0	1	0
1	3	2	1
2	4	0	2

 

HEDGEHOG_DIST

i \ j	0	1	2
0	3	0	0
1	2	1	0
2	1	0	1

무사히 비버 굴에 도착한 도치 :)

 

 

예제 입력 2의 경우 KAKTUS 출력

i \ j	0	1	2
0	D	.	*
1	.	.	.
2	.	.	S

 

WATER_TIMING

i \ j	0	1	2
0	0	1	0
1	3	2	1
2	4	3	0

 

HEDGEHOG_DIST

i \ j	0	1	2
0	0	0	0
1	0	0	0
2	2	1	0

물에 빠진 불쌍한 도치 :(

 

 

 

---

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int R, C;

    static String[] MAP;

    static int[][] WATER_TIMING, HEDGEHOG_DIST;

    static boolean[][] VISIT;

    static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        WATER_TIMING = new int[R][C];
        HEDGEHOG_DIST = new int[R][C];

        MAP = new String[R];
        for(int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            MAP[i] = st.nextToken();
        }
    }

    static void initVisitArray() {
        if(VISIT == null) {
            VISIT = new boolean[R][C];
        } else {
            for(int i = 0; i < R; i++) {
                for(int j = 0; j < C; j++) {
                    VISIT[i][j] = false;
                }
            }
        }
    }

    static void calWaterTiming() {
        Queue<Integer> que = new LinkedList<>();

        initVisitArray();
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(MAP[i].charAt(j) == '*') {
                    que.add(i);
                    que.add(j);
                    VISIT[i][j] = true;
                }
            }
        }

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

            for(int i = 0; i < 4; i++) {
                int nx = x + DIRECTION[i][0];
                int ny = y + DIRECTION[i][1];

                if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if(VISIT[nx][ny]) continue;
                if(MAP[nx].charAt(ny) == '.') {
                    VISIT[nx][ny] = true;
                    WATER_TIMING[nx][ny] = WATER_TIMING[x][y] + 1;
                    que.add(nx);
                    que.add(ny);
                }
            }
        }
    }

    static void moveHedgehog() {
        Queue<Integer> que = new LinkedList<>();

        initVisitArray();
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(MAP[i].charAt(j) == 'S') {
                    HEDGEHOG_DIST[i][j] = 0;
                    VISIT[i][j] = true;
                    que.add(i);
                    que.add(j);
                }
            }
        }

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

            for(int i = 0; i < 4; i++) {
                int nx = x + DIRECTION[i][0];
                int ny = y + DIRECTION[i][1];

                if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if(VISIT[nx][ny]) continue;
                if(WATER_TIMING[nx][ny] != 0 && WATER_TIMING[nx][ny] <= HEDGEHOG_DIST[x][y] + 1) continue;

                if(MAP[nx].charAt(ny) == '.'|| MAP[nx].charAt(ny) == 'D') {
                    que.add(nx);
                    que.add(ny);
                    VISIT[nx][ny] = true;
                    HEDGEHOG_DIST[nx][ny] = HEDGEHOG_DIST[x][y] + 1;
                }
            }
        }
    }

    static void pro() {
        calWaterTiming();

        moveHedgehog();

        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(MAP[i].charAt(j) == 'D') {
                    if(HEDGEHOG_DIST[i][j] == 0) sb.append("KAKTUS");
                    else sb.append(HEDGEHOG_DIST[i][j]);
                }
            }
        }

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }

}