[Baekjoon] 16954_움직이는 미로 탈출

Gold III

문제(출처: https://www.acmicpc.net/problem/16954)

---

< 움직이는 미로 탈출 >

 

문제 풀이

 

이 문제는 벽이 1초마다 아래로 한 칸씩 내려간다는 부분이 중요하다.

1초마다 아래로 한 칸씩 움직이는 부분을 실제로 배열에 저장하지 않고 인덱스로 접근하여 이동할 위치가 빈칸인지 벽인지 확인한다.

- 자세한 풀이는 다음에 시간이 날 때 작성

 

 

 - my solution (Java)

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

public class _16954_ { // 움직이는 미로 탈출
	static boolean arr[][], visited[][], result;
	static int dx[] = { 0, -1, 1, 0, 0, -1, -1, 1, 1 };
	static int dy[] = { 0, 0, 0, -1, 1, -1, 1, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		arr = new boolean[8][8];
		visited = new boolean[8][8];
		result = false;

		for (int i = 0; i < 8; i++) {
			String str = bf.readLine();
			for (int j = 0; j < 8; j++) {
				if (str.charAt(j) == '#') {
					arr[i][j] = true; // 벽
				}
			}
		}
		search(7, 0, 0);

		if (result)
			System.out.println(1);
		else
			System.out.println(0);
	}

	private static void search(int start_x, int start_y, int depth) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { start_x, start_y, depth });

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int i = 0; i < 9; i++) {
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];
				if (x >= 0 && x < 8 && y >= 0 && y < 8  ) {
					if(x-temp[2]>=0 && arr[x-temp[2]][y]) continue;

					if(i!=0 && visited[x][y]) continue;
					if (x - (temp[2]+1) >= 0) {
						if (!arr[x - (temp[2]+1)][y]) {
							if (x == 0 && y == 7) {
								result = true;
								break;
							}
							visited[x][y] = true;
							queue.add(new int[] { x, y, temp[2] + 1 });

						}
					} else {
						if (x == 0 && y == 7) {
							result = true;
							break;
						}
						visited[x][y] = true;
						queue.add(new int[] { x, y, temp[2] + 1 });
					}
				}
			}
			if (result)
				break;
		}
	}
}

 

• Main
  • arr : 체스판 상태 입력
  • visited : 방문 여부
  • search 함수를 통해 왼쪽 아랫칸부터 시작
  • 결과 출력
• search 
  
  • queue에 시작 위치위치와 이동 횟수 저장 {x, y, depth} 
  • queue가 빌 때까지 반복 -> 현재 위치, 상하좌우, 대각선 이동 -> 1초마다 벽이 이동하는 위치를 계산해서 이동하려는 위치가 빈칸이라면 이동하기

---

생각🤔

---