[BAEKJOON_3055 - JAVA] 탈출

이해가 되지않아 자세한 도움이 필요하거나 오류가 있는 경우 댓글을 남겨주세요.

문제

www.acmicpc.net/problem/3055

3055번: 탈출

 

 

풀이

• 처음에는 큐를 4개 사용해서 풀었지만,
  가독성이 떨어지고 자료의 입출력이 많아져 size를 활용한 반복문의 조건으로 변경해서 풀이.
• 가독성을 위해 메소드 단위로 나누어 설계.
• 65번째줄의 while문 조건의 설계를 고슴도치가 이동할 곳이 없게 했지만,
  비버의 굴을 발견했음에도 멈추는 조건을 설정 하지않아 해당 오류를 찾는데 시간이 오래걸렸다.
  95번째 줄의 비버의 굴에 도착했을 경우 큐를 비우는 조건을 추가하여 해결.
  → 스택이나 큐같은 자료구조를 사용할 경우 clear를 신경쓰자!

 

 

과정

1. 입력을 받으면서 고슴도치와 물의 위치를 큐에 삽입.
2. while문으로 물을 채우는 함수인 spread와 고슴도치의 이동인 bfs 함수 호출.
   (고슴도치가 이동할 곳이 없는 경우 혹은 비버의 굴까지 도착 못할 경우)
3. 물이 찰 위치로는 고슴도치가 이동하지 못하기 때문에 물을 채우는 spread 먼저 호출.
4. 4방 탐색을 진행 하면서 물이 찰 수 있는 '.'인 경우 큐에 삽입과 map의 정보 '*'로 변경.
5. spread 함수 종료 후 bfs함수 호출.
6. 마찬가지로 4방 탐색을 진행하며, 이동가능 여부를 판단하는 isMove 함수 활용.
   방문한적이 없는 경우 큐에 삽입.
7. 탐색 중 비버의 굴을 발견하는 경우 고슴도치의 큐를 비우고 리턴.
8. 출력

 

 

알고리즘 지식

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

JAVA코드

package BaekJoon_2020_12_30__2021_01_06;

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

/**
 * @packageName : BaekJoon_2020_12_30__2021_01_06
 * @fileName : BJ_3055_탈출.java
 * @author : Mingeon
 * @date : 2020. 12. 31.
 * @language : JAVA
 * @classification :
 * @time_limit : 1sec
 * @required_time : 01:10 ~ 03:05
 * @submissions : 5
 * @description 94
 * 95번째 줄을 찾느라 1시간 반이 걸렸다. 
 * 큐나 스택 같은 자료구조를 이용한 반복문을 사용할 경우에는 조건을 완료했을 때, 반드시 clear를 할 것!
 */

public class BJ_3055_탈출 {

	static int R; // R행
	static int C; // C열
	static char[][] map; // 숲의 정보
	static boolean[][] visited;// 방문 관리
	static int minCnt; // 최소 시간
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static Queue<Pos> moveQ = new LinkedList<Pos>();
	static Queue<Pos> waterQ = new LinkedList<Pos>();

	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][C];
		visited = new boolean[R][C];
		minCnt = Integer.MAX_VALUE;
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				char c = str.charAt(j);
				map[i][j] = c;
				// 고슴도치의 위치
				if (c == 'S') {
					moveQ.offer(new Pos(i, j));
					visited[i][j] = true;
				}
				// 물의 위치
				else if (c == '*') {
					waterQ.offer(new Pos(i, j));
				}
			}
		}

		// 이동 횟수
		int move = 0;
		while (!moveQ.isEmpty()) {
			spread(); // 물이 찰 예정인 칸으로 이동이 불가하므로 먼저 실행.
			bfs(++move); // 고슴도치의 이동
		}

		System.out.println(minCnt == Integer.MAX_VALUE ? "KAKTUS" : minCnt);
		br.close();
	}

	// 고슴도치의 이동 탐색
	private static void bfs(int move) {
		int cnt = moveQ.size();

		// 기존의 크기 동안
		while (cnt-- > 0) {
			Pos pos = moveQ.poll();
			int row = pos.row;
			int col = pos.col;

			// 4방 탐색
			for (int d = 0; d < 4; d++) {
				int nextRow = row + dy[d];
				int nextCol = col + dx[d];

				// 범위 검사 && 고슴도치의 이동 가능 검사
				if (isIn(nextRow, nextCol) && isMove(nextRow, nextCol)) {

					// 비버의 굴 발견
					if (map[nextRow][nextCol] == 'D') {
						minCnt = move; // 최소값 탐색 완료
						moveQ.clear(); // 호출하는 곳의 while문 조건을 위한 Queue 초기화
						return; // 종료
					}

					// 방문한적이 없는 경우
					if (!visited[nextRow][nextCol]) {
						moveQ.offer(new Pos(nextRow, nextCol)); // 임시 Queue에 삽입
						visited[nextRow][nextCol] = true; // 방문 체크
					}
				}
			}
		}
	}

	// 물을 채울 곳을 탐색
	private static void spread() {
		int cnt = waterQ.size();

		// 기존의 크기 동안
		while (cnt-- > 0) {
			Pos waterPos = waterQ.poll();
			int row = waterPos.row;
			int col = waterPos.col;

			// 4방 탐색
			for (int d = 0; d < 4; d++) {
				int nextRow = row + dy[d];
				int nextCol = col + dx[d];

				// 범위 검사 && 물이 찰 수 있는 경우
				if (isIn(nextRow, nextCol) && map[nextRow][nextCol] == '.') {
					waterQ.offer(new Pos(nextRow, nextCol));
					map[nextRow][nextCol] = '*';
				}
			}
		}
	}

	// 고슴도치의 이동 가능 여부
	private static boolean isMove(int row, int col) {
		if (map[row][col] == '.' || map[row][col] == 'D') {
			return true;
		}
		return false;
	}

	// 범위 검사
	private static boolean isIn(int row, int col) {
		if (row < 0 || row >= R || col < 0 || col >= C) {
			return false;
		}
		return true;
	}

}

class Pos {
	int row;
	int col;

	public Pos(int row, int col) {
		this.row = row;
		this.col = col;
	}

}