[백준] 3055번 탈출 - Java, 자바

3055번 탈출

난이도

골드 4

문제 설명

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

요구사항

• R*C 배열
• '.': 빈칸, '*': 물, 'X': 돌(통과 X), 'D': 비버의 굴(통과), 'S': 고슴도치 위치
• 매 분마다 인접 4방향으로 물이 퍼짐.
• 고슴도치가 인접 4방향으로 1칸씩 이동 가능하다. 하지만, 물에 잠긴 곳은 이동할 수 없으며, 다음 분에 물이 찰 예정인 칸도 이동 불가.
• 고슴도치가 목표(S)로 도달할 수 있는 최소 시간(분) 출력, 목표로 도달할 수 없을 시 "KAKTUS" 출력.

접근 방식

고슴도치가 목표로 도달할 수 있는 최소 시간을 구하는 문제이기 때문에 BFS 탐색을 이용하여 물의 퍼짐과 고슴도치의 이동을 시뮬레이션하면 쉽게 풀 수 있을 것이라고 생각하였다.
특히, 고슴도치는 다음 분에 물이 찰 예정인 칸에 이동할 수 없기 때문에 물의 퍼짐을 먼저 실행한 후 고슴도치의 이동을 구현하였다.
고슴도치가 방문한 칸에 다시 방문하지 않도록 visited 배열을 이용하여 방문한 칸을 체크하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point{
int x;
int y;

public Point(int x, int y) {
    this.x = x;
    this.y = y;
}
}

public class Main{
static int r, c, answer=0;
static boolean flag = false;
static char[][] arr;
static int[][] visited;
static int[] dx = {0, -1, 0, 1};
static int[] dy = {-1, 0, 1, 0};
static Queue water = new LinkedList<>();
static Queue q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
arr = new char[r][c];
visited = new int[r][c];
for(int i=0; i<r; i++){
String line = br.readLine();
for(int j=0; j<c; j++){
arr[i][j] = line.charAt(j);
// 물이 차있는 지역
if(arr[i][j] == '*') water.offer(new Point(i,j));
// 고슴도치 위치
if(arr[i][j] == 'S') {
arr[i][j] = '.';
visited[i][j] = 1;
q.offer(new Point(i,j));
}
}
}
BFS();
if(flag) System.out.println(answer+1);
else System.out.println("KAKTUS");
}

static void BFS(){
    while (!q.isEmpty()){
        // 물 확장
        int size = water.size();
        for(int i=0; i<size; i++){
            Point nowWater = water.poll();
            for(int j=0; j<4; j++){
                int nx = nowWater.x + dx[j];
                int ny = nowWater.y + dy[j];
                if(nx>=0 && nx<r && ny>=0 && ny<c){
                    if(arr[nx][ny] == '.') {
                        arr[nx][ny] = '*';
                        water.offer(new Point(nx, ny));
                    }
                }
            }
        }

        // 고슴도치 이동
        size = q.size();
        for(int i=0; i<size; i++){
            Point now = q.poll();
            for(int j=0; j<4; j++){
                int nx = now.x + dx[j];
                int ny = now.y + dy[j];
                if(nx>=0 && nx<r && ny>=0 && ny<c){
                    // 고슴도치가 비버의 굴로 도착하면 리턴
                    if(arr[nx][ny] == 'D') {
                        flag = true;
                        return;
                    }
                    if(arr[nx][ny] == '.' && visited[nx][ny] == 0){
                        visited[nx][ny] = 1;
                        q.offer(new Point(nx, ny));
                    }
                }
            }
        }
        answer++;
    }

}
}

복잡도 분석

물 BFS: O(RC)
고슴도치 BFS: O(RC)
총 O(RC), 메모리 O(RC)

느낀점

이 문제를 통해서 시뮬레이션을 해야될 주체가 2개일 때 BFS로 탐색하는 패턴을 체득할 수 있어서 좋은 연습이 되었다. "물 퍼짐" -> "고슴도치 이동"과 같이 BFS를 같은 레벨에서 교차로 탐색하여 처리하니 “다음 분에 물이 찰 칸으로는 이동 불가” 규칙을 자연스럽게 만족시킬 수 있었다."
지형 배열을 'S'로 덮어쓰면 물 확장이 막혀 오답이 될 수 있다는 것을 알 수 있었다.
전체 복잡도는 O(RC)로 안정적이고, 이중 시뮬레이션에 대한 감각을 키울 수 있던 문제였다.