[알고리즘] 백준16954 움직이는 미로 탈출 - 자바

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

16954번: 움직이는 미로 탈출

 

 

[풀이 코드]

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

public class BOJ_16954_움직이는미로탈출 {
	static ArrayList<char[]> list;
	static Queue<Point> q = new LinkedList<>();
	static int[] dy = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
	static int[] dx = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
	static int N = 8;
	static boolean[][] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		list = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			list.add(br.readLine().toCharArray()); //맵을 계속 바꿔줘야해서 ArrayList로 선언
		}
		
		System.out.println(bfs());
	}
	
	static int bfs() {
		q.offer(new Point(N-1, 0));
		
		while(!q.isEmpty()) {
			visited = new boolean[N][N]; // 맵이 계속 바뀌니까 그때마다 초기화를 해줘야 함..
			
			int size = q.size(); // 무조건! 해줘야 함 for문안에서 poll을 하면 size가 변경이 되니까
			for(int s=0; s<size; s++) {
				Point point = q.poll();
				
				if(list.get(point.y)[point.x] == '#') continue; // 벽을 만나면 큐에서 다음 좌표를 부르기
				if(point.y == 0 && point.x == N-1) return 1; // 목적지에 도달했다면
				
				for(int d=0; d<9; d++) {
					int y = point.y + dy[d];
					int x = point.x + dx[d];
					if(y>=0 && x>=0 && y<N && x<N) {
						if(list.get(y)[x] == '.' && !visited[y][x]) {
							visited[y][x] = true;
							q.offer(new Point(y, x));
						}
					}
				}
			}
			
			list.remove(N-1); // 맨 아래에 행 삭제
			list.add(0, new char[] {'.', '.', '.', '.', '.', '.', '.', '.'}); //맨 위에 행 추가
			
		}
		return 0;
	}
	
	static class Point{
		int y, x;
		Point(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
	

}

• 정말 정말 신경 쓸게 많은 문제였다. 심지어 예전에 풀어본 문제인데 또 막혀서 쩔쩔맸다.

list = new ArrayList<>();
		
for(int i=0; i<N; i++) {
	list.add(br.readLine().toCharArray()); //맵을 계속 바꿔줘야해서 ArrayList로 선언
}

• 먼저, 이 문제에서는 평소와 다르게 입력을 받았다. ArrayList에 char형 배열을 받도록 했는데 이유는 좌표가 이동하고 난 뒤에 벽이 내려와야 한다. 그래서 큐에 이동 가능한 좌표를 다 넣어줬다면 배열을 수정하기 위해 arraylist를 활용했다.

 

static int bfs() {
    q.offer(new Point(N-1, 0));

    while(!q.isEmpty()) {
        visited = new boolean[N][N]; // 맵이 계속 바뀌니까 그때마다 초기화를 해줘야 함..

        int size = q.size(); // 무조건! 해줘야 함 for문안에서 poll을 하면 size가 변경이 되니까
        for(int s=0; s<size; s++) {
            Point point = q.poll();

            if(list.get(point.y)[point.x] == '#') continue; // 벽을 만나면 큐에서 다음 좌표를 부르기
            if(point.y == 0 && point.x == N-1) return 1; // 목적지에 도달했다면

            for(int d=0; d<9; d++) {
                int y = point.y + dy[d];
                int x = point.x + dx[d];
                if(y>=0 && x>=0 && y<N && x<N) {
                    if(list.get(y)[x] == '.' && !visited[y][x]) {
                        visited[y][x] = true;
                        q.offer(new Point(y, x));
                    }
                }
            }
        }

        list.remove(N-1); // 맨 아래에 행 삭제
        list.add(0, new char[] {'.', '.', '.', '.', '.', '.', '.', '.'}); //맨 위에 행 추가

    }
    return 0;
}

• bfs함수 안 반복문에서 중요했던 건 두 가지이다.
  
  1. size = q.size() 를 설정한 후 큐에 담긴 좌표를 처리하는 것이다. 
  쉽게 말하면 벽이 떨어지기 전 맵에서 이동 가능한 좌표를 큐에 넣어준다. 그리고 모든 벽이 1칸씩 떨어진 바뀐 맵에서 이전에 큐에 넣어줬던 좌표들을 꺼내서 일괄 처리해주기 위함이다.
  
  2. visted = new boolean[N][N] 를 계속 while문이 다시 시작할 때마다 초기화해주는데 어떻게 보면 당연하다. 이동거리는 제자리를 포함해서 9곳을 갈 수 있고 왔던 곳을 다시 가야 벽을 피할 수 있는 상황이 있을 것이다. (문제에는 해당 예제 입력이 없음!)