[백준 알고리즘] 3055번: 탈출_Java

[문제]​

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

​

[입력]

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

​

[출력]

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

​

​[예제]

 

---

>문제 풀이

D : 비버 굴

S : 고슴도치 위치

* : 물

. : 빈 곳

X : 돌

char mat[][]에 입력값들을 저장하면서, 물의 위치와 시작 위치를 큐에 담아줍니다.

물의 위치를 먼저 쭉 담고, 시작 위치를 담도록 구현했는데 물 먼저 bfs를 해주고 고슴도치가 움직여야 정답값을 효율적으로 구할 수 있기 때문입니다.

(고슴도치가 움직여도 그 다음에 물에 잠기면 처리가 좀 더 복잡해집니다.)

​

물이 상하좌우로 확장해나갈 때는 mat범위 내에서 발생하며 값도 *으로 변경해줍니다.

고슴도치는 빈 곳으로만 이동해서 D에 도달해야합니다. 최종적으로 D에 도달했을 때, 몇 분 걸렸는지를 출력해야하는데 dp[][]값에 시작 위치부터 카운트해서 최단거리로 D에 도달하는 시간을 구했습니다.

​

위의 과정을 다 돌렸는데도, D에 도달하지 못했다면 "KAKTUS"를 출력합니다.

​

---

저는 처음에 고슴도치가 먼저가고 물이 확장되도록 구현했는데, 이렇게 했더니 queue.size()만큼만 for문을 반복하게 하는데에서 어려움을 겪었습니다.

 

https://arinnh.tistory.com/40?category=934581 

[프로그래머스] level 2: 가장 먼 노드_Java

이 문제를 풀었던 것처럼 풀어보려고 했는데, 잘 안되어서 코드를 수정했습니다.

 

 

>전체 코드

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int R, C;
	static char[][] mat;
	static int[][] dp;
	static Queue<Point> queue;
	
	static int time=0;
	
	public static void main(String[] args) {
		Point start = null;
		String str="";
		
		Scanner scan= new Scanner(System.in);
		
		R= scan.nextInt();
		C= scan.nextInt();
		mat= new char[R][C];
		dp= new int[R][C];
		queue= new LinkedList<>();
		
		//빈 곳: . // 물: * // 돌: X //비버 굴: D // 고슴도치: S
		for(int i=0; i<R; i++) {
			str= scan.next();
			for(int j=0; j<C; j++) {
				mat[i][j]= str.charAt(j);
				if(mat[i][j]=='S') {
					start= new Point(i, j, 'S');
				}else if(mat[i][j]=='*') {
					queue.add(new Point(i, j, '*'));
				}
			}
		}
		queue.add(start);
		
		bfs();
	}//main
	
	
	static int[] dx= {-1, 0, 1, 0};
	static int[] dy= {0, -1, 0, 1};
	
	//고슴도치가 비버 굴로 가야함(순서:물->고슴도치)
	public static void bfs() {
		Point p;
		int nx, ny;
		
		while(!queue.isEmpty()) {
			p= queue.poll();
			if(p.type=='D') {
				System.out.println(dp[p.x][p.y]);
				return;
			}

			for(int i=0; i<4; i++) {
				nx= p.x+dx[i];
				ny= p.y+dy[i];

				if(!check(nx, ny)) continue;				
				if(p.type=='*') {
					if(mat[nx][ny]=='.'||mat[nx][ny]=='S') {
					mat[nx][ny]= '*';
					queue.add(new Point(nx, ny, '*'));
					}
				}else { //p.type=='.'
					if(mat[nx][ny]=='.'||mat[nx][ny]=='D') {
						if(dp[nx][ny]>0) continue;
						dp[nx][ny]= dp[p.x][p.y]+1;
						queue.add(new Point(nx, ny, mat[nx][ny]));
					}
				}
			}
		}//while
		System.out.println("KAKTUS");
	}

	//범위 확인
	public static boolean check(int x, int y) {
		if(x<0||x>=R) return false;
		if(y<0||y>=C) return false;
		return true;
	}
	
	static class Point{
		int x, y;
		char type;
		public Point(int x, int y, char type) {
			this.x= x;
			this.y= y;
			this.type= type;
		}
	}
}

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

3055번: 탈출