백준_탈출_3055

// 알고리즘

1. 탐색문제

 -> 최단 거리를 구하기 때문에 BFS 탐색

 

2. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 는 조건

 -> 물웅덩이 부터 탐색을 시작함

 

3. 물웅덩이와 고슴도치의 이동을 다르게 봐야하기 때문에 3차원 방문배열 사용

 

4. 물웅덩이 1 사이클 => 고슴도치 1 사이클 씩 번갈아가면서 탐색

 -> 각각 어레이리스트를 만들어 다음번 시행되어야할 위치를 큐에넣지말고 어레이리스트에 저장

 -> 한 사이클(while)이 끝나면 저장된 어레이리스트를 큐에 집어넣고 리스트 초기화

 

5. 도착할 때 까지 무한으로 실행

 -> 탈출 조건은 고슴도치가 도착점에 도달하지 못하고 이동할 곳도 없을 경우 (큐의 사이즈가 0일 때)

package baekjoon;

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

public class 탈출_3055 {

	static char[][] map;
	static int R, C, ans, r, c;
	static int[] dr = { 1, -1, 0, 0 };
	static int[] dc = { 0, 0, 1, -1, };
	static boolean[][][] v;
	static Queue<Point> q, water;
	static ArrayList<Point> wList, sList;

	static class Point {
		int r, c, cnt;

		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}

	}

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

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new char[R][];
		v = new boolean[2][R][C];
		q = new LinkedList<Point>();
		water = new LinkedList<Point>();
		wList = new ArrayList<Point>();
		sList = new ArrayList<Point>();

		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().toCharArray();
		}


		// 알고리즘
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if (map[i][j] == 'S') {
					v[0][i][j] = true;
					q.add(new Point(i, j, 0));
				} else if (map[i][j] == '*') {
					v[0][i][j] = true;
					v[1][i][j] = true;
					water.add(new Point(i, j));
				}
			}
		}

		bfs();
		System.out.println(ans == 0 ? "KAKTUS" : ans);

	}

	private static void bfs() {

		while (true) {

			// 물 먼저
			Point w = null;
			while (!water.isEmpty()) {
				w = water.poll();
				for (int k = 0; k < 4; k++) {
					int nr = w.r + dr[k];
					int nc = w.c + dc[k];

					if (nr < 0 || nc < 0 || nr >= R || nc >= C || v[1][nr][nc])
						continue;
					if (map[nr][nc] == 'D' || map[nr][nc] == 'X')
						continue;
					v[0][nr][nc] = true;
					v[1][nr][nc] = true;
					wList.add(new Point(nr, nc));
				}
			}

			water.addAll(wList);
			wList.clear();

			// 고슴도치
			Point d = null;
			while (!q.isEmpty()) {
				d = q.poll();

				for (int k = 0; k < 4; k++) {
					int nr = d.r + dr[k];
					int nc = d.c + dc[k];

					if (nr < 0 || nc < 0 || nr >= R || nc >= C || v[0][nr][nc] || v[1][nr][nc])
						continue;
					if (map[nr][nc] == 'X') continue;
					if (map[nr][nc] == 'D') {
						ans = d.cnt + 1;
						return;
					}
					v[0][nr][nc] = true;
					sList.add(new Point(nr, nc, d.cnt + 1));
				}

			}

			q.addAll(sList);
			sList.clear();

			if (q.size() == 0)
				break;
		}

	}

}

 

※ 3차원 방문배열을 사용하는 탐색에 한 사이클씩 돌려야하는 문제라 지금 까지 풀어봤던 문제 2~3개를 섞어논듯한 문제였다. 다행히 비슷한 유형의 문제를 많이풀어봐서 풀이시간은 30~40분정도로 짧게 끝남.

탐색문제의 실력을 체크하기에 좋은 문제라고 생각한다.