#3055 탈출
난이도 : 골드 5
유형 : 그래프 / BFS
▸ 문제
사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.
▸ 입력
첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.
▸ 출력
첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.
문제 풀이 🖋
고슴도치가 비버의 굴로 갈 수 있는 가장 빠른 시간을 출력하는 그래프 문제이므로, BFS탐색을 사용해야겠다.
문제 조건
Map : R x C (최대 50x50)
구하는 값 : S -> D 가장 빠른시간
a) '*' 물은 1초에 상하좌우로 퍼짐 (단, D와 X는 이동 x)
b) 'S'는 상하좌우 중 1칸만 이동 (단, D와 X와 *로 이동 x)
c) 그리고 추가로, 비버는 다음에 물이 찰 공간으로도 이동할 수가 없다.
이 문제의 중요한 점은 한 싸이클을 이해하는 것이다.
한 싸이클 내부는 다음과 같다.
1) 물이 이동 -> 비버의 이동 (c조건 충족)
2) 한 싸이클에 (비버의 Queue 크기), (물의 Queue크기) 만큼만 돌린다.
첫 번째는 예제 2번으로 예를 들면 쉽다.
원래 비버와 물이 동시에 이동하는 것이지만 물의 이동을 더 빠르게 한 후 비버를 이동시키면 자연스레 조건을 충족시켜줌을 알 수 있다. 그래서 1) 물의 이동과 2) 비버의 이동을 나누어서 로직을 짜야한다.
❍ Cycle 1
물 -> 비버
D * * D * *
. . * . . *
. . S . S S
❍ Cycle 2
물 -> 비버
D * * D * *
. * * . * *
. S S S S S
❍ Cycle 3
물 -> 비버
D * * D * *
* * * * * *
S S S S S S -> 이동 x 종료
그리고 중요한 두 번째는 BFS탐색을 할 때 Queue의 크기를 받아 그 크기만큼 돌려야한다는 것이다.
왜냐하면 비버의 이동과 물의 이동에 순서가 있기 때문이다.
Cycle 1: 물 이동 1 -> 비버 이동 1
Cycle 2: 물 이동 2 -> 비버 이동 2
int size = wq.size();
for(int t=0; t<size; t++) {
...
}
해당 조건을 걸어두지 않고 while문으로 queue가 채워지는 대로 반복을 돌리게되면 순서가 지켜지지 않아 올바른 답이 나오지 않을 것이다.
Cycle 1: 물 이동 1 -> 비버 이동 1-1 -> 물 이동 2 -> 비버 이동 1-2 ...
Cycle 2: 물 이동 4 -> 비버 이동 2-1 -> ...
풀이 코드 ✔︎
// #3055 graph 탈출 (BFS)
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int r,c, res = -1;
static int[][] map;
static boolean[][] check, wcheck;
static int[] dx = { -1, 1 ,0 ,0 };
static int[] dy = { 0 ,0 , -1, 1};
static Queue<Node> q = new LinkedList<>();
static Queue<Node> wq = 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());
map = new int[r][c];
check = new boolean[r][c];
wcheck = new boolean[r][c];
for(int i=0; i<r; i++) {
String[] line = br.readLine().split("");
// D: 26, S: 41, *: 0, .: 4, X: 46
for(int j=0; j<c; j++) {
map[i][j] = line[j].charAt(0)-42;
if(!line[j].equals(".")) {
if(line[j].equals("S")) {
q.add(new Node(i,j,0));
}else if(line[j].equals("*")) {
wq.add(new Node(i,j,0));
}
}
}
}
solve();
System.out.println(res == -1? "KAKTUS" : res);
}
static void solve() {
while(true) {
waterMove();
int size = q.size();
if(size ==0) break;
for(int t=0; t<size; t++) {
Node nxt = q.poll();
int nmove = nxt.move;
// 고슴도치 이동
for(int i=0; i<4; i++) {
int nx = nxt.x +dx[i];
int ny = nxt.y +dy[i];
if(nx<0 || ny<0 || nx>r-1 || ny>c-1) continue;
if(check[nx][ny]) continue;
// 도착
if(map[nx][ny] == 26) {
// System.out.println("goal! "+ (nmove+1));
res = nmove+1;
return;
}
if(map[nx][ny] == 4 && !wcheck[nx][ny]) {
check[nx][ny] = true;
// System.out.println("gosum :" +nmove+ "::"+nx+","+ny);
q.add(new Node(nx,ny,nmove+1));
}
}
}
}
}
// 물 이동
static void waterMove() {
int size = wq.size();
for(int t=0; t<size; t++) {
Node nxt = wq.poll();
for(int i=0; i<4; i++) {
int nx = nxt.x +dx[i];
int ny = nxt.y +dy[i];
if(nx<0 || ny<0 || nx>r-1 || ny>c-1) continue;
if(wcheck[nx][ny]) continue;
if(map[nx][ny] == 4) {
wcheck[nx][ny] = true;
// System.out.println("water :" +nmove+ "::"+nx+","+ny);
wq.add(new Node(nx,ny,0));
}
}
}
}
static class Node{
int x;
int y;
int move;
public Node(int x, int y, int move) {
this.x =x;
this.y =y;
this.move =move;
}
}
}
그리고 풀이를 하고나니 Node클래스에 있는 move를 없애고 solve()함수 내에서 count변수를 생성하여 사용하는 것이 더 효율적일 것 같다. 물의 이동에서는 사용하지 않기 때문에 메모리 낭비 같다.
'Dot Algo∙ DS > PS' 카테고리의 다른 글
[BOJ] 백준 9252번 LCS2 (Java) (0) | 2021.05.04 |
---|---|
[BOJ] 백준 9251번 LCS (Java) (0) | 2021.05.04 |
[프로그래머스] 2021 카카오/ 신규 아이디 추천 (Java) (0) | 2021.05.03 |
[BOJ] 백준 2629번 양팔저울 (Java) (0) | 2021.05.03 |
[BOJ] 백준 1922번 네트워크 연결 (Java) (0) | 2021.05.03 |