🔗 문제 링크
https://www.acmicpc.net/problem/3055
🔍 문제 설명
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
⚠️ 제한사항
-
50보다 작거나 같은 자연수 R과 C가 주어진다.
-
안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.
🗝 풀이 (언어 : Java)
상당히 복잡한 문제였다. 풀이를 공부하고 작성해 보았다. 미리 물을 확산시켜서 각 지점마다 침수되려면 몇초가 걸리는지 적은 배열을 만들어줘서 이용하는 문제이다. 물이 터지는 지점이 여러개가 가능하기 때문에, 미리 물의 시작점을 찾아두고 그 지점들만 큐에넣어 불필요한 BFS호출을 줄인다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Main {
private void escape(int n, int m, char[][] forest) {
// 방향 배열, 해당 지점에 물이 몇초에 오는지 값을 넣은 2차원 배열, 방문 배열
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int[][] waterArr = new int[n][m];
boolean[][] waterVisit = new boolean[n][m];
// 물의 시작점 위치, 고슴도치 시작위치 구하기
List<int[]> waters = new ArrayList<>();
int[] start = new int[2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
waterArr[i][j] = -1; // 물 배열 기본 원소 -1로
if (forest[i][j] == '*') {
waters.add(new int[]{i, j}); // 시작점의 좌표를 리스트에 기록
waterArr[i][j] = 0; // 물 시작점은 0초만에 물에 잠김
} else if (forest[i][j] == 'S') {
start[0] = i;
start[1] = j;
} else if (forest[i][j] == 'D') {
waterArr[i][j] = 2500;
}
}
}
// 물의 시작 지점들을 큐에 넣고 BFS를 실행
Queue<int[]> flood = new LinkedList<>();
for (int[] water : waters)
flood.offer(water);
// 시간, BFS
int waterTime = 0;
// 해당 지점에 물이 몇초에 오는지 값을 넣은 2차원 배열 만들기
while (!flood.isEmpty()) {
waterTime++;
int size = flood.size();
for (int i = 0; i < size; i++) {
int[] area = flood.poll();
int x = area[0], y = area[1];
for (int j = 0; j < 4; j++) {
int nx = x + dirs[j][0], ny = y + dirs[j][1];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || waterVisit[nx][ny] || forest[nx][ny] != '.')
continue;
waterArr[nx][ny] = waterTime;
waterVisit[nx][ny] = true;
flood.offer(new int[]{nx, ny});
}
}
}
boolean[][] goVisit = new boolean[n][m];
// 고슴도치의 위치 넣기
flood.offer(new int[]{start[0], start[1]});
waterArr[start[0]][start[1]] = 0; // 시작점 아래 if문 통과위해 고슴도치 시작점 0 초기화
int goTime = -1;
while (!flood.isEmpty()) {
goTime++;
int size = flood.size();
for (int i = 0; i < size; i++) {
int[] here = flood.poll();
int x = here[0], y = here[1];
// 고슴도치 동굴 발견시 정답 출력
if (forest[x][y] == 'D') {
System.out.print(goTime);
return;
}
for (int j = 0; j < 4; j++) {
int nx = x + dirs[j][0], ny = y + dirs[j][1];
// 범위를 벗어나거나, 이미 방문한 지역이면 스킵
if (nx < 0 || nx >= n || ny < 0 || ny >= m || goVisit[nx][ny])
continue;
// 갈 수 없는 곳이거나, 이미 침수된 지역일 경우 스킵
if (waterArr[nx][ny] != -1 && waterArr[nx][ny] <= goTime + 1)
continue;
if (forest[nx][ny] != '.' && forest[nx][ny] != 'D')
continue;
goVisit[nx][ny] = true;
flood.offer(new int[]{nx, ny});
}
}
}
System.out.print("KAKTUS");
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
char[][] forest = new char[n][m];
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < m; j++)
forest[i][j] = s.charAt(j);
}
br.close();
new Main().escape(n, m, forest);
}
}