[BOJ/Java] 3055 : 탈출

문제

 

풀이

이렇게 1초에 한 칸씩 이동할 때는 bfs를 사용한다 / 물이 넘칠 때도 bfs를 사용했다 

고슴도치가 먼저 이동하고 물이 차도록 구현해서 고슴도치가 이동할 때 물이 이미 있는 곳 / 물이 찰 예정인 곳은 이동하지 않도록 했는데 굳이 이렇게 안 해도 물이 먼저 차고 고슴도치가 이동하면 물이 이미 있는 곳만 고려해주면 된다

물이 찰 예정인 곳까지 고려하느라 비버의 굴에 거의 다 왔을 때 물이 바로 옆에 있으면 이동하지 못하는 문제가 생겼다 / 이동할 곳이 비버의 굴이면 물이 옆에 있어도 이동할 수 있도록 비버의 굴인지 여부를 먼저 따져주었다

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] dir = { { 0, -1 }, { -1, 0 }, { 1, 0 }, { 0, 1 } };
	static int r, c;
	static char[][] map;
	static int s_x, s_y;
	static boolean[][] checkFlood;
	static boolean[][] checkMove;
	static int count = 1;
	static Queue<Node> queueForMove = new LinkedList<>();
	static Queue<Node> queueForWater = new LinkedList<>();

	private static class Node {
		private int x, y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int getX() {
			return this.x;
		}

		public int getY() {
			return this.y;
		}
	}

	public static int move() {

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] == 'S' && !checkMove[i][j]) {
					queueForMove.offer(new Node(i, j));
				}
			}
		}
		
		if(queueForMove.isEmpty()) return -1;
		
		while (!queueForMove.isEmpty()) {
			Node node = queueForMove.poll();
			int move_x = node.x;
			int move_y = node.y;
			checkMove[move_x][move_y] = true;
			
			for (int d = 0; d < 4; d++) {

				int dx = move_x + dir[d][0];
				int dy = move_y + dir[d][1];

				if (dx < 0 || dy < 0 || dx >= r || dy >= c)
					continue;
				
				if (map[dx][dy] == 'D') {
					return count;
				}
				
				if (isNearWater(dx, dy))
					continue;
				
				if (map[dx][dy] == '.')
					map[dx][dy] = 'S';

			}
			
			
		}
		count++;
		return 0;

	}

	private static void flood() { // 물이 한칸씩 불어남
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (map[i][j] == '*' && !checkFlood[i][j]) {
					queueForWater.offer(new Node(i, j));
				}
			}
		}

		while (!queueForWater.isEmpty()) {
			Node node = queueForWater.poll();
			int water_x = node.x;
			int water_y = node.y;
			checkFlood[water_x][water_y] = true;
			for (int d = 0; d < 4; d++) {

				int dx = water_x + dir[d][0];
				int dy = water_y + dir[d][1];

				if (dx < 0 || dy < 0 || dx >= r || dy >= c) {
					continue;
				}
				if (map[dx][dy] == 'X' || map[dx][dy] == 'D')
					continue;

				map[dx][dy] = '*';
			}

		}

	}

	private static boolean isNearWater(int x, int y) { // 물이 있거나 물이 찰 예정이면 true를 리턴하는 함수
		// 해당 좌표가 물인지
		if (map[x][y] == '*')
			return true;
		// 해당 좌표가 물이 찰 예정인지
		for (int d = 0; d < 4; d++) {

			int dx = x + dir[d][0];
			int dy = y + dir[d][1];

			if (dx < 0 || dy < 0 || dx >= r || dy >= c) {
				continue;
			}

			if (map[dx][dy] == '*') {// 물이 찰 예정이면
				return true;
			}
			if (map[x][y] == '*')
				return true;
		}
		return false;
	}

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine(), " ");
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new char[r][c];
		// map 정보 입력받기
		for (int i = 0; i < r; i++) {
			String temp = in.readLine();
			for (int j = 0; j < c; j++) {
				map[i][j] = temp.charAt(j);
				if (map[i][j] == 'S') {
					s_x = i;
					s_y = j;
				}
			}
		}

		checkFlood = new boolean[r][c];
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				checkFlood[i][j] = false;
			}
		}
		checkMove = new boolean[r][c];
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				checkMove[i][j] = false;
			}
		}
		int result = 0;
		while (true) {
			result = move();
			if(result == count) {
				System.out.println(result);
				break;
			}
			else if(result == -1) {
				System.out.println("KAKTUS");
				break;
			}
			flood();
		}
			

	}
	
	//디버깅용
	static void show() {
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		System.out.println("----");
	}

}