백준 3055 탈출

문제

---

3055번: 탈출 (acmicpc.net)

해결방법

---

• BFS 각각 BFS 단계별로 진행하며 먼저 해당 단계의 물을 퍼트리고 해당 단계의 고슴도치가 이동할 수 있는 위치를 모두 구한다. 그 때 고슴도치가 이동할 다음 위치가 D에 해당하면 전체 반복문을 종료한다.
  
• 주의점 문제에서 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 라고 되어 있으니 BFS를 수행하며 물의 위치를 먼저 구해 놓고 고슴도치가 이동 가능한 칸을 구해야 한다.
  

동작과정

---

1. 고슴도치의 초기 위치와 물들의 초기 위치를 저장한다.
2. 전체 반복문을 돌면서 단계를 저장하고 먼저 퍼뜨릴 물들을 받아와서 맵에 물을 퍼뜨린다.
3. 그 후 현재 단계에 존재할 수 있는 고슴도치의 위치들에 대해 다음 위치를 찾는다. 이때 비버의 굴을 발견하면 현재의 단계 + 1을 결과로 주고 전체 반복문을 종료한다.
4. 출력 시 result 값이 Integer.MAX_VALUE 라는 것은 고슴도치가 비버의 굴에 도달하지 못한 것이므로 KAKTUS 를 출력한다.

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static class Point {
		int y;
		int x;

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

	private final static int[][] D = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(in.readLine());

		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		char[][] map = new char[R][C];
		boolean[][] visited = new boolean[R][C];

		// 맵을 입력받고 시작지점과 물의 위치를 저장
		Point start = null;
		Queue<Point> waters = new ArrayDeque<>();
		for (int i = 0; i < R; i++) {
			String line = in.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = line.charAt(j);
				if (map[i][j] == 'S') {
					start = new Point(i, j);
					map[i][j] = '.';
				}
				else if(map[i][j] == '*') {
					waters.offer(new Point(i, j));
				}
			}
		}

		Queue<Point> q = new ArrayDeque<>();
		q.offer(start);

		int result = Integer.MAX_VALUE;
		int step = 0;

		external: while (!q.isEmpty()) {
			
			// 물 먼저 처리 -> 물이 찰 예정인 곳에는 고슴도치가 못가기 때문에
			// 다음 물의 위치들을 저장하기 위한 newWaters
			List<Point> newWaters = new ArrayList<>();
			// 현재 모든 물이 있는 곳을 저장하고 있는 waters 에서 각 위치를 꺼낸다.
			while(!waters.isEmpty()) {
				Point water = waters.poll();
				// 4방향을 돌면서 해당 방향에 물이 이동할 수 있는 지를 체크하고 이동할 수 있으면 물로 바꿔주고 newWaters에 추가함
				for (int d = 0; d < 4; d++) {
					int wy = water.y + D[d][0];
					int wx = water.x + D[d][1];

					if (isInBound(wy, wx, R, C) && map[wy][wx] == '.') {
						newWaters.add(new Point(wy, wx));
						map[wy][wx] = '*';
					}
				}
			}
			// 다음단계에 물을 처리하기 위해 newWaters의 좌표들을 waters에 저장
			for(Point water : newWaters)
				waters.offer(water);

			// bfs의 다음 단계에 해당하는 고슴도치가 갈 수 있는 좌표값들을 모두 넣어놓기 위한 list
			List<Point> list = new ArrayList<>();

			// 현재 단계에 해당하는 좌표값들이 q에 들어있고 그것들을 모두 처리
			while (!q.isEmpty()) {
				Point now = q.poll();

				// 고슴도치가 갈 수 있는 4방향 탐색
				for (int d = 0; d < 4; d++) {
					int sy = now.y + D[d][0];
					int sx = now.x + D[d][1];

					// 고슴도치가 향하는 방향이 범위 안이고 방문하지 않은 곳이라면
					if (isInBound(sy, sx, R, C) && !visited[sy][sx]) {
						// 방문할 곳이 빈칸이면 list에 추가하고 방문 표시를 해줌
						if (map[sy][sx] == '.') {
							list.add(new Point(sy, sx));
							visited[sy][sx] = true;
						}

						// 방문할 곳이 목적지면 현재 step에 1을 더한 값을 result로 저장하고 전체 반복문 종료
						else if (map[sy][sx] == 'D') {
							result = step + 1;
							break external;
						}
					}
				}
			}
			
			// 고슴도치의 다음단계 위치에 해당하는 값들을 가진 list의 모든 내용을 q에 추가함
			for(Point p : list)
				q.add(p);
			
			// 다음 단계
			step++;
		}

		// 길을 못 찾은 경우
		if(result == Integer.MAX_VALUE)
			out.write("KAKTUS");
		// 길을 찾은 경우
		else
			out.write(result+"");
		
		out.flush();
	}

	// 범위 체크를 위한 함수
	private static boolean isInBound(int y, int x, int R, int C) {
		if (y >= 0 && y < R && x >= 0 && x < C)
			return true;
		else
			return false;
	}
}