백준 3055 탈출 (Java)

1. 문제 링크

3055번: 탈출

 

2. 문제 및 입출력예제

 

3. 문제 풀이

고슴도치는 물이 찰 예정인 곳으로 갈 수 없기 때문에 먼저 물을 채우는 방향으로 진행했다.

물을 채우고 bfs 탐색을 하면 고슴도치가 갈 수 있는 곳을 큐에 넣는다.

큐가 비었는데도 도착하지 못했다면 KAKTUS를 출력한다.

 

4. 코드

import java.awt.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Queue;

public class Main {
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	static int N, M, endX, endY;
	static int[] dx = {0,0,-1,1}, dy = {-1,1,0,0};
	static char[][] map;
	static ArrayList<Point> list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new char[N][M];
		
		int startX = -1, startY = -1;
		list = new ArrayList<>();
		char temp;
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				temp = str.charAt(j);
				map[i][j] = temp;
				if(temp == 'D') {
					endX = i;
					endY = j;
				}
				else if (temp=='S'){
					startX = i;
					startY = j;
				}
				else if(temp=='*') {
					list.add(new Point(i, j));
				}
			}
		}
		
		int result = move(startX, startY);
		if(result == -1) {
			System.out.println("KAKTUS");
		}
		else {
			System.out.println(result);
		}
		
	}
	
	private static int move(int x, int y) {
		int cnt = 0;
		Queue<Point> queue = new ArrayDeque<>();
		queue.offer(new Point(x, y));
		boolean[][] visit = new boolean[N][M];
		visit[x][y] = true;
		
		while(true) {
			water();
			int size = queue.size();
			if(size == 0) break;
			for(int i=0;i<size;i++) {
				Point p = queue.poll();
				int pX = p.x;
				int pY = p.y;
				
				if(pX==endX && pY==endY) {
					return cnt;
				}
				for(int d=0;d<4;d++) {
					int X = pX + dx[d];
					int Y = pY + dy[d];
					if(!check(X, Y)) continue;
					if(map[X][Y] == '*' || visit[X][Y]) continue;
					
					queue.offer(new Point(X, Y));
					visit[X][Y] = true;
				}
			}
			cnt++;
		}
		return -1;
	}

	private static void water() {
		HashSet<Point> set = new HashSet<>(); 
		for(Point p: list) {
			for(int d=0;d<4;d++) {
				int X = p.x+dx[d];
				int Y = p.y+dy[d];
				if(!check(X, Y)) continue;
				if(map[X][Y] == '.') {
					set.add(new Point(X, Y));
					map[X][Y] ='*';
				}
			}
		}
	
		list.addAll(set);
	}

	private static boolean check(int x, int y) {
		if(x<0 || x>=N || y<0 || y>=M || map[x][y]=='X') {
			return false;
		}
		return true;
	}
}