[백준 : JAVA] 움직이는 미로 탈출하기

https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

---

 

 

[1회차] 11월 10일, 문제 추천받음

문제 접근 방법 (사용 자료구조, 알고리즘)

 

입력
(1) 8개 줄에 걸쳐서 주어지는 체스판의 상태를 walls[8][8][8](3차원 int 배열)로 저장
(2) 가장 처음에 나온 벽('#')이 가장 위에 있으므로 이것을 찾으면 firstIdx를 해당 열로 변경해준다.(1번만)

로직
(0) 만약 firstIdx가 변하지 않았다면(-1) 벽이 없으므로 무조건 도달가능한 상태이므로 1을 출력하고 종료한다
(1) [벽의 움직임] 벽은 무조건 1초가 지나면 아래로 내려간다. 그래서 이것을 시간에 따라 3차원 배열안에 미리 계산을 해서 넣어주었다.
(2) [욱제의 움직임] 가만히 있는 경우를 포함해서 9방 탐색을 한다.
(3) [욱제의 움직임] 범위를 벗어난 경우, 가려고 하는 다음 위치에 벽이 있는 경우, 가려고 하는 다음 위치에 1초 후에 벽이 위치하는 경우에는 큐에 넣어주지 않는다.
(4) 도달하려고 하는 위치에 도달하면 true 를 반환하고 정답을 출력한다.

 

 

메모리 & 시간

메모리를 너무 많이 써서 메모리를 줄이고 시간도 줄이는 방법을 생각해보아야겠다

문제 추천자는 80ms 로 끊음

 

 

 

코드

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

public class Main {
	static int firstIdx = -1, dir[][] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {0, -1}, {1, -1}, {-1, 0}, {-1, 1}, {-1, -1}};
	static int walls[][][];
	
	static class Pos{
		int x, y, time;

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

	public static void main(String[] args) throws Exception{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		// 1. 입력
		walls = new int[8][8][8];
		for (int i = 0; i < 8; i++) {
			String line = in.readLine();
			for (int j = 0; j < 8; j++) {
				char ch = line.charAt(j);
				if(ch == '#') walls[0][i][j] = 1;
				if(firstIdx == -1) firstIdx = i;
			}
		}
		
		// 2. 로직 : 욱제의 캐릭터는 가장 왼쪽 아랫 칸(7, 0)에 있고, 이 캐릭터는 가장 오른쪽 윗 칸(0, 7)으로 이동해야 한다.
		if(firstIdx != -1) wallGravitiy(new Pos(0, 0, 0));
		else {
			System.out.println(1);
			System.exit(0);
		}
		
		// 3. 로직 & 출력
		// 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력
		System.out.println(bfs()? 1: 0);
	}

	private static boolean wallGravitiy(Pos o) {
		// 1초마다 모든 벽('#')이 아래에 있는 행으로 한 칸씩 내려가고 (i++)
		// 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다
		for (int t = 1; t < 8 - firstIdx; t++) {
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					if(i + 1 < 8 && walls[t-1][i][j] == 1) {
						walls[t][i+1][j] = 1;
					}
				}
			}
		}
	
		return true;
	}

	private static boolean bfs() {
		// 욱제의 캐릭터는 가장 왼쪽 아랫 칸(7, 0)에 있고, 이 캐릭터는 가장 오른쪽 윗 칸(0, 7)으로 이동해야 한다.
		Queue<Pos> q = new LinkedList<>();
		q.offer(new Pos(7, 0, 0));
		boolean visited[][] = new boolean[8][8];
		visited[7][0] = true;
		
		while(!q.isEmpty()) {
			// 욱제 움직임
			Pos ook = q.poll();
			int time = ook.time;
			
			// 1초에 인접한 한 칸 or 대각선 방향으로 인접한 한 칸 or 움직이지 않음
			for (int i = 0; i < 9; i++) {
				int dx = ook.x + dir[i][0];
				int dy = ook.y + dir[i][1];
				
				// 이동할 때는 빈 칸으로만 이동('.')
				if(!inBound(dx, dy)|| (time < 7 && (walls[time][dx][dy] == 1 || walls[time + 1][dx][dy] == 1))) continue;
				if(dx == 0 && dy == 7) return true;
				
				q.offer(new Pos(dx, dy, time + 1));
			}
		}
		
		return false;
	}
	
	static boolean inBound(int x, int y) {
		if(x < 0 || y < 0 || x >= 8 || y >= 8) return false;
		return true;
	}
}

 

 

 

 

문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)

문제 해석	문제 접근	코드 구현
20분	20분	1시간 30분