[BOJ 16954] 움직이는 미로 탈출 (Java)

BOJ 16954 움직이는 미로 탈출

문제풀이

아무것도 아닌 간단한 BFS 문제인데 4시간 가량을 속썩였다... 그냥 시키는대로 하면된다. 사람이 이동하고 벽이 이동하고 조건에 따라 걸러내면된다.

내가 오랫동안 발견하지 못한 부분은 바로 첫 위치인 (7, 0)을 큐에 넣을 때 방문 체크를 해서는 안된다는 것이다!!!

• 움직임 중에서 가만히 있기가 있는데 처음에 방문 체크를 해버리면 1초 때 가만히 있을 수가 없다!

나머지는 어려운 부분이 없다. 위 문제를 알아내기까지 다양한 코드를 살펴보았는데 그 중 몇가지 구현 방법에 대해서 얘기하자면

• BFS 수행중 시간을 나타내는 변수를 가지고 있는 것, 객체 또는 BFS 함수 내에 가지고 있는다.

  • 맵을 실제로 움직이지 않고 시간에 따라 참조하는 위치를 다르게 할 수 있다.
    if(nr - t >= 0 && map[nr - t][nc] == '#')
if(nr - t - 1 >= 0 && map[nr - t - 1][nc] == '#')

  • 방문체크를 좌표와 시간의 조합으로 한다.

  • 8초가 지나면 모든 벽이 없어지기 때문에 8초 경과 후에도 큐에 남아있는 것이 있다면 무조건 가능한 것이다.

효율적이거나 멋진 코드가 아니라 문제의 조건을 그대로 나타내는 직관적인 코드를 첨부하였다.

구현코드

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

public class Main {
	
	static class Node {
		int r, c;
		
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static int[][] dir = {{0, 0}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
	static Queue<Node> q;
	static char[][] map;
	static boolean[][] visited;
	static int ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		q = new LinkedList<>();
		map = new char[8][8];
		visited = new boolean[8][8];
		ans = 0;
		
		for(int r = 0 ; r < 8 ; ++r) {
			char[] line = br.readLine().toCharArray(); 
			for(int c = 0 ; c < 8 ; ++c) {
				map[r][c] = line[c];
			}
		}
		
		bfs();
		
		System.out.println(ans);
	}

	private static void bfs() {
		q.offer(new Node(7, 0));
		
		while(!q.isEmpty()) {
			int size = q.size();
			visited = new boolean[8][8];
            
			for(int i = 0 ; i < size ; ++i) {
				Node cur = q.poll();
                
				if(map[cur.r][cur.c] == '#') continue;
                                if(cur.r == 0) {
                                    ans = 1;
                                    return;
                                }
				
				for(int d = 0 ; d < 9 ; ++d) {
					int nr = cur.r + dir[d][0];
					int nc = cur.c + dir[d][1];
					
					if(nr < 0 || nr >= 8 || nc < 0 || nc >= 8) continue;
					if(visited[nr][nc] || map[nr][nc] == '#') continue;

                    			q.offer(new Node(nr, nc));
					visited[nr][nc] = true;
				}
			}
			moveWall();
		}
	}
    
	private static void moveWall() {
		for(int r = 7 ; r >= 0 ; --r) {
			for(int c = 0 ; c < 8 ; ++c) {
				if(r == 0) map[r][c] = '.';
				else map[r][c] = map[r - 1][c];
			}
		}
	}
}