[백준 3055] - 탈출

 

문제

• 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다.
  • 이 숲에는 고슴도치가 한 마리 살고 있다.
  • 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
• 티떱숲의 지도는 R행 C열로 이루어져 있다.
  • 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다.
  • 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
• 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다.
  • (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다.
  • 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.
  • 물과 고슴도치는 돌을 통과할 수 없다.
  • 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
• 티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
• 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.
  • 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

 

입력

• 첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
  • 다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

 

출력

• 첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다.
  • 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

 

 

솔루션

• 고슴도치가 동굴까지 이동할 수 있는 최소 거리를 구하는 문제이다.
• 고슴도치와 웅덩이를 시작점으로 하여 각각 BFS를 수행하면 된다.
  • 웅덩이가 다음번에 퍼지는 곳은 고슴도치가 이동할 수 없다는 조건이 있으므로, BFS는 웅덩이 다음 고슴도치 순서로 한다.
  • 웅덩이 ('*') 가 퍼질때마다 좌표 값을 확인한 뒤 돌멩이 ('X') 또는 동굴 ('D') 이 아니라면 (고슴도치 ('S') 또는 ('.')) 좌표 값을 웅덩이 ('*') 로 바꿔준다.
  • 고슴도치 ('S') 가 움직일때마다 좌표 값을 확인한 뒤 돌멩이 ('X') 와 웅덩이 ('*') 가 아니라면 좌표 값을 고슴도치 ('S') 로 바꿔주고 이전 좌표 값은 ('.') 로 바꿔준다.
    
    • 만약 고슴도치가 이동한 곳이 동굴 ('D') 라면 현재까지 지난 시간 (minute) 를 반환하고 수행을 종료한다.
  • 웅덩이와 고슴도치가 모두 움직였다면, 현재 고슴도치가 동굴까지 갈 수 있는지 여부를 확인한다.
    • 동굴 사방이 돌 또는 웅덩이로 둘러싸여있는지
    • 현재 지도에서 고슴도치 ('S') 가 존재하는지
      • 두 가지 중 하나라도 해당이 된다면 동굴로 갈 수 있는 경우는 없으므로 수행을 종료한다.
  • 그 이외의 상황이라면 다시 처음부터 위 과정 (웅덩이와 고슴도치를 이동) 을 수행한다.
• 그림을 통해 확인해보자. 

첫 번째 예시

• 위 그림에서 1분씩 순서대로 진행하면 아래와 같을 것이다.

두 번째 예시

• 두 번째 예시를 진행해보면 아래와 같을 것이다.
  • 결국 고슴도치는 동굴에 도달하지 못하게 된다.

• 세 번째, 네 번째 예시도 마찬가지로 진행하되 돌멩이는 웅덩이, 고슴도치가 모두 지나갈 수 없다는 점을 유의해야 한다.

 

Code

• 전체코드 : Solution_3055

1분당 고슴도치가 움직이고, 물이 퍼지는 과정을 진행하는 함수

public static String PerMinute() {
    minute++;
    SpreadPuddles();
    Move();
    
    if (cave == null)
        return Integer.toString(minute);
    else if (!isPossible() || hedgehog.size() == 0)
        return "KAKTUS";
    else
        return "";
}

 

웅덩이가 퍼지도록 하는 함수

public static void SpreadPuddles() {
    Queue<Point> queue = new LinkedList<>();
 
    queue.addAll(puddles);
    puddles.clear();
 
    while (!queue.isEmpty()) {
        Point puddle = queue.poll();
 
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + puddle.x;
            int ny = dy[i] + puddle.y;
 
            if (0 <= nx && nx < N && 0 <= ny && ny < M) {
                if (map[nx][ny] == '.' || map[nx][ny] == 'S') {
                    map[nx][ny] = '*';
                    puddles.add(new Point(nx, ny));
                }
            }
        }
    }
}

 

고슴도치가 움직이는 함수

public static void Move() {
    Queue<Point> queue = new LinkedList<>();
 
    queue.addAll(hedgehog);
    hedgehog.clear();
 
    while (!queue.isEmpty()) {
        Point h = queue.poll();
 
        if (map[h.x][h.y] == 'S')
            map[h.x][h.y] = '.';
 
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + h.x;
            int ny = dy[i] + h.y;
 
            if (0 <= nx && nx < N && 0 <= ny && ny < M) {
                if (map[nx][ny] == 'D') {
                    cave = null;
                    return;
                }
 
                if (!visited[nx][ny] && map[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    map[nx][ny] = 'S';
                    hedgehog.add(new Point(nx, ny));
                }
            }
        }
    }
}

 

동굴 주변을 확인하여 동서남북 모두 막혔는지 여부를 확인하는 함수

public static boolean isPossible() {
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + cave.x;
        int ny = dy[i] + cave.y;
 
        if (0 <= nx && nx < N && 0 <= ny && ny < M) {
            if (map[nx][ny] == '*' || map[nx][ny] == 'X')
                continue;
 
            return true;
        }
    }
 
    return false;
}

 

결과