[백준] 16954 : 움직이는 미로 탈출 - JAVA [자바]

안녕하세요.

오늘은 움직이는 미로 탈출 문제를 풀어보도록 하겠습니다.

 

 

📌 접근

1초가 지난 뒤에는 벽 모양이 바뀌므로, 같은 시간대(초)의 case들을 전부 처리한 한 뒤 벽을 움직여야합니다.

따라서 bfs를 사용해야 합니다.

 

탐색 모양은 dx, dy 배열을 이용하여 정의하였습니다.

배열을 벗어나는 위치는 isInRange() 함수로 판별합니다.

 

큐가 빌 때까지 큐에서 원소를 꺼내는 bfs의 조건에,

현재 큐의 사이즈만큼만 꺼내고 다음 시간대(초)의 원소들을 탐색하는 조건을 추가하여 코드를 짰습니다.

이는 동시간대의 원소를 전부 처리한 뒤에 벽을 움직이기 위함입니다.

 

 

 

💻 풀이

// hyeblee
import java.io.*;
import java.util.*;

// 최단 경로는 bfs로

public class Main {
	public static final int SIZE = 8;
	// 제자리 + 8방향 (↑, ↗, →, ↘, ↓, ↙, ←, ↖) 순서대로 정의
	public static final int[] dx = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };
	public static final int[] dy = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };

	public static char[][] chess = new char[SIZE][SIZE];
	public static int second = 0;

	public static class Node {
		int x;
		int y;

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

	public static int bfs() {
		Queue<Node> queue = new ArrayDeque<>();
		queue.offer(new Node(0, 7));
		while (!queue.isEmpty()) {
			int size = queue.size();

			for (int i = 0; i < size; i++) { // 현재 시간대의 노드들 순회
				Node cur = queue.poll();
				if (chess[cur.y][cur.x] == '#')
					continue;
				if (cur.x == 7 && cur.y == 0)
					return 1;
				for (int j = 0; j < 9; j++) { // cur에서 이동할 수 있는 점 큐에 넣기
					int x = cur.x + dx[j];
					int y = cur.y + dy[j];
					if (isInRange(x, y) && chess[y][x] != '#') {
						queue.offer(new Node(x, y));
					}
				}
			}

			// 다음 시간대로 넘어가기 전에 벽 이동하기
			moveWall();
		}
		return 0;
	}

	public static void moveWall() {
		// 맨 아래부터 채워야 원하는 대로 미룰 수 있다.
		for (int i = SIZE - 1; i > 0; i--) {
			chess[i] = Arrays.copyOf(chess[i - 1], 8);
		}
		chess[0] = "********".toCharArray();

	}

	public static boolean isInRange(int x, int y) {
		return x >= 0 && x < 8 && y >= 0 && y < 8;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 8; i++) {
			String input = br.readLine();
			chess[i] = input.toCharArray();
		}
		System.out.println(bfs());
	}
}

🤔 고민했던 점 & 어려웠던 부분

 

욱제가 움직이지 않고 제자리에 있는 케이스를 고려하지 못했다.

 

벽을 미는 연산을 위에서부터 해서 오류가 났다.

-> 위에서부터가 아니라 아래서부터 해야 올바른 연산을 할 수 있다.

 

벽을 적절한 시점에서 밀어야하는데, 이를 제대로 판단하지 못했다.

 

 

 

< 벽을 미는 시점 >

현재 시점에 있는 노드를 다 탐색하고, 이 노드들의 인접노드인 다음 단계로 가기 전에 밀면 됩니다.

 

-> 큐에서 노드를 꺼내기 전에 사이즈를 측정합니다.

-> 이 사이즈가 같은 시간대(초) 에 있는 원소들입니다.

-> 큐 사이즈만큼만 꺼내고 난 뒤에 벽을 밀어주면 됩니다.