[백준 3055 - JAVA] 탈출

3055번: 탈출

티떱숲에 일어난 홍수를 피해 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 길을 출력하라!

전형적인 BFS문제로, 물과 고슴도치의 이동의 Queue를 두개 활용한다.

 

풀이 방법

1. Input과정에서 hedgehog와 water 두개의 큐에 각각 고슴도치와 물의 위치를 넣는다.

2. hedgehog 큐가 0이 되거나 비버의 굴에 도착할때까지 bfs.

3. bfs는 time이 증가한 후 water 먼저 진행한다.

   3-1. 범위를 벗어나거나 돌에 마주치면 continue

   3-2. 이미 물로 범람한 구역이거나 비버의 굴인 경우에도 continue

   3-3. 고슴도치가 지나간 위치거나 빈 구역일 경우 map을 *로 표시하고 que에 삽입 - 방문 표시가 된다.

4. hedgehog의 경우 비슷하나 비버의 굴인 경우 return true로 탈출

5. 비버의 굴에 도착하지 못하고 bfs가 종료되는 경우 이동할 수 없는 케이스로 “KAKTUS”를 출력한다.

import java.io.*;
import java.util.*;

public class Main {
	public static int N, M, time;
	public static char[][] map;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static Queue<int[]> water;
	public static Queue<int[]> hedgehog;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		water = new LinkedList<int[]>();
		hedgehog = new LinkedList<int[]>();
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 'S') {
					hedgehog.offer(new int[] {i, j});
				}else if (map[i][j] == '*') {
					water.offer(new int[] {i, j});
				}
			}
		}
		System.out.println(bfs()? time:"KAKTUS");
	}
	
	public static boolean bfs() {
		while(!hedgehog.isEmpty()) {
			time++;
			int size = water.size();
			for (int i = 0; i < size; i++) {
				int[] cur = water.poll();
				for (int j = 0; j < 4; j++) {
					int nx = cur[0] + dx[j];
					int ny = cur[1] + dy[j];
					
					if (!isBoundary(nx, ny) || map[nx][ny] == 'X') continue;
					if (map[nx][ny] == '*' || map[nx][ny] == 'D') continue;
					
					map[nx][ny] = '*';
					water.offer(new int[] {nx, ny});
				}
			}
			
			size = hedgehog.size();
			for (int i = 0; i < size; i++) {
				int[] cur = hedgehog.poll();
				for (int j = 0; j < 4; j++) {
					int nx = cur[0] + dx[j];
					int ny = cur[1] + dy[j];
					
					if (!isBoundary(nx, ny) || map[nx][ny] == 'X') continue;
					if (map[nx][ny] == '*' || map[nx][ny] == 'S') continue;
					if (map[nx][ny] == 'D') return true;
					
					map[nx][ny] = 'S';
					hedgehog.offer(new int[] {nx, ny});
				}
			}
		}
		return false;
	}
	
	public static boolean isBoundary(int nx, int ny) {
		if (nx < 0 || nx >= N || ny < 0 || ny >= M) return false;
		return true;
	}
	
}