[BFS] 16954번 - 움직이는 미로 탈출

안수진·2024년 7월 30일

Baekjoon

목록 보기

27/55

[백준] 16954. 움직이는 미로 탈출

📝 나의 풀이

문제를 보자마자 BFS 라는 것은 파악했으나
미로에서 이동하지 못하는 벽이 움직인다는 조건 때문에 많이 헤맸다.

캐릭터가 움직인 후, 벽이 움직인다

BFS로 다음으로 이동할 경로를 탐색한 후에 벽을 이동하는 함수를 호출해야 하는데 어느 지점에서 호출해야 할지 감이 오지 않았다.

📌 문제 조건

캐릭터는 상하좌우, 대각선, 제자리 총 9가지 방향으로 이동 가능하다.
1초 동안 캐릭터가 이동한 후, 벽이 한칸 아래로 내려온다.
캐릭터가 이동 후, 해당 동일한 자리에 벽이 있으면 캐릭터는 더이상 움직일 수 없다.
벽이 마지막 행에서 내려갈 때는 소멸한다.

출발지(왼쪽 최하단): (7, 0)
목적지(오른쪽 최상단): (0, 7)

😎 코드 로직

캐릭터와 벽의 위치를 저장하기 위해 class Node {x, y}을 선언한다.
캐릭터의 BFS 탐색
- 큐에서 꺼낸 현재 위치가 벽인 경우 탐색 종료
- 큐에서 꺼낸 현재 위치가 목적지인 경우 탐색 종료
- 9방향으로 탐색하여 가능한 위치만 큐에 추가한다.
  가능한 위치? 맵 이내 벽#이 아닌 위치

현재 레벨의 노드들을 모두 탐색

    int size = q.size();
	for (int s = 0; s < size; s++) {
    	Node tmp = q.poll();
    	// 노드 탐색 작업
	}

다음 레벨의 노드들을 큐에 추가

    for (int i = 0; i < 9; i++) {
    int newX = x + dx[i];
    int newY = y + dy[i];
    if (isValid(newX, newY) && map[newX][newY] == '.') {
        q.offer(new Node(newX, newY));
    }
}

1초간의 캐릭터 이동 종료

맵의 벽 이동
- 최하단 위치부터 벽을 아래로 이동시킨다.
- 최상단은 모두 .으로 채운다.

큐에서 꺼낸 노드의 위치Queue.poll() = 현재 캐릭터의 위치

💻 제출 코드

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

class Node{
	int x;
	int y;
	
	Node(int x, int y){
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return this.x;
	}
	
	public int getY() {
		return this.y;
	}
	
	public void setX(int x) {
		this.x = x;
	}
}

public class Main {
	
    static char[][] map = new char[8][8];
    static List<Node> walls = new ArrayList<>();
    static int[] dx = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    static int[] dy = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    
    
    public static boolean isValid(int x, int y) {
    	return x >= 0 && x < 8 && y >= 0 && y < 8;
    }
    
    public static void moveWall() {
    	for(int i=6;i>=0;i--){
            for(int j=0;j<8;j++){
                map[i+1][j] = map[i][j];
            }
        }
    	
        //첫번째 행은 모두 '.'으로 변경
        for(int i=0;i<8;i++){
            map[0][i] = '.';
        }
    }
    
    public static int bfs(int x, int y) {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(x, y));
    	
    	while(!q.isEmpty()) {
    		
    		int size = q.size();
    		
    		for(int s = 0; s < size; s++) {
    			Node tmp = q.poll();
        		x = tmp.getX();
        		y = tmp.getY();
    			
    			if(map[x][y] == '#') continue;
    			if(x == 0 && y == 7) return 1;
        		
        		for(int i = 0; i < 9; i++) {
        			int newX = x + dx[i];
        			int newY = y + dy[i];

    		    	if(isValid(newX, newY)) {
    		    		if(map[newX][newY] == '.')
    		    			q.offer(new Node(newX, newY));
    		    	}
    		    	
        		}
    		}
    		moveWall();
    	}

    	return 0;
    	
    }
    

	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();
			for(int j = 0; j < 8; j++) {
				map[i][j] = input.charAt(j);

			}
		}
		
		System.out.println(bfs(7, 0));
		
	}

}