[백준] 16954번 - 움직이는 미로 탈출 (Java)(○)

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

16954번: 움직이는 미로 탈출

 

<문제 해석>

1. 체스판의 크기는 8 x 8이다. 모든 판은 빈 칸(.)과 벽(#)으로 되어 있다.

2. 가장 왼쪽 아래 칸에서 가장 오른쪽 윗 칸으로 이동해야 한다.

3. 1초마다 모든 벽이 아래에 있는 행으로 한칸씩 이동한다. 만약 가장 아래 였으면 벽이 사라진다.

4. 캐릭터는 인접한 한 칸 또는 대각선으로 이동하거나, 현재 위치에 서 있을 수 있다.

5. 1초 동안 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다.

6. 벽이 캐릭터가 있는 칸으로 이동하면 캐릭터는 이동할 수 없다.

7. 캐릭터가 목적지까지 이동할 수 있으면 1, 없으면 0을 출력한다.

 

<풀이 #1>

1. 이동거리를 구할 필요가 없으니 class Node {x, y}만 선언한다.

2. 캐릭터의 BFS탐색을 한번 하고, 그 후에 맵의 벽을 이동한다.

3. 맵의 벽 이동 함수 구현

  - 캐릭터가 8방향으로 탐색을 끝내고 나면 맵 업데이트 함수를 호출한다.

  - 경로를 재탐색할 필요가 없으니 원본맵을 업데이트한다.

  - 이중 for문을 아래 행부터 돌려서 #를 만나면 map[r+1][c] = # 를 한다.

4. 캐릭터의 이동조건

  - 8개 방향으로 이동 or 이동하지 않는다.

  - 큐에서 꺼냈는데 그 위치에 벽이 있으면 탐색을 중지한다.

  - 방문배열 사용하지 않는다. (이동거리를 구하는게 아니기 때문)

5. 가지치기 조건

  - 맵 범위를 벗어나면

  - 벽이면

 

5. 종료조건

  - 맵에 벽이 더 이상 없을 때 -> 1출력

  - 벽이 캐릭터가 있는 칸으로 이동하면 -> 0출력

 

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

public class Main {
    static int R = 8, C = 8;
    static char map[][];
    static boolean visited[][];
    //static int dx[] = {-1, 0, 1, 0}; // 상하좌우 4방향
    //static int dy[] = {0, 1, 0, -1};
    static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1, 0}; // 상하좌우 & 대각선 & 제자리 9방향
    static int dy[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};

    class Node {
        int x, y;
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    void moveWall() {
        for (int i=7; i>=0; i--) {
            for (int j=0; j<8; j++) {
                if (map[i][j] == '#') {
                    map[i][j] = '.';
                    if (i != 7) {
                        map[i+1][j] = '#';
                    }
                }
            }
        }
        //printMap();
    }

    boolean foundWall() {
        for (int i=0; i<8; i++) {
            for (int j=0; j<8; j++) {
                if (map[i][j] == '#')
                    return true;
            }
        }
        return false;
    }

    void printMap() {
        for (int i=0; i<8; i++) {
            for (int j=0; j<8; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("---------------");
    }

    void BFS() {
        Queue<Node> Q = new LinkedList<>();
        Q.add(new Node(7, 0)); // 시작점 큐에 넣기
        //visited[7][0] = true;
        while(!Q.isEmpty()) {
            int count = Q.size();
            while(count > 0) {
                Node now = Q.poll();
                count--;
                //System.out.println("Queue: poll("+now.x+", "+now.y+") : count = "+count);
                // 그 위치에 벽이 있으면 탐색 패스
                if (map[now.x][now.y] == '#') continue;
                // 맵에 벽이 없으면 종료
                if (!foundWall()) {
                    System.out.println(1);
                    return;
                }
                //도착지 도착하면 종료
                if (now.x == 0 && now.y == 7) {
                    System.out.println(1);
                    return;
                }
                // 제자리에 가만히 있는 경우를 위해 방문배열 초기화
                visited[now.x][now.y] = false;
                // 9개 방향으로 캐릭터 이동
                for (int i=0; i<9; i++) {
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];
                    // 가지치기
                    if (nx<0 || nx>=8 || ny<0 || ny>=8) continue; // 맵 범위 벗어나면 패스
                    if (map[nx][ny] == '#') continue; // 벽을 만나면 패스
                    if (visited[nx][ny]) continue; // 방문한 곳이면 패스
                    // 큐에 넣기
                    Q.add(new Node(nx, ny));
                    visited[nx][ny] = true;
                    //System.out.println("Queue: add("+nx+", "+ny+")");
                }
            }
            // 벽을 아래로 이동
            moveWall();
            //printMap();
        }
        System.out.println(0);
    }

	void Solve() {
        visited = new boolean[8][8];
        BFS();
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        //StringTokenizer st = new StringTokenizer(br.readLine());
        //N = Integer.parseInt(st.nextToken());//열
        //M = Integer.parseInt(st.nextToken());//행
        map = new char[8][8];
        for (int i=0; i<8; i++) {
            //st = new StringTokenizer(br.readLine());
            String str = br.readLine();
            for (int j=0; j<8; j++) {
                //map[i][j] = Integer.parseInt(st.nextToken());
                map[i][j] = str.charAt(j);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}

 

<피드백>

1. 제자리에 가만히 있는 경우를 빼먹어서 8개 방향이 아닌 9개 방향 탐색하는 것으로 추가했다.

2. 큐에 들어간 것들을 다 꺼내서 탐색을 하면 1초가 흐른다. 그 뒤에 벽을 움직여야 한다.

그러므로 Queue.size() 만큼 Q.poll()을 해야지 새로 추가되는 것들의 영향을 받지 않는다.

3. 한 턴이 끝날때마다 방문배열을 초기화 해야 한다. 왜냐하면 벽이 움직이기 때문에 새로운 경로가 생길 수 있기 때문이다.

 

<예제 5번 풀이>

........
........
........
........
#.......
.#######
#.......
........

 

 

 

<풀이 #2>

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

public class Main {
    static int R = 8, C = 8;
    static char map[][];
    static boolean visited[][];
    static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1, 0}; // 상하좌우 & 대각선 & 제자리 9방향
    static int dy[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};

    class Node {
        int x, y;
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    void moveWall() {
        for (int i=7; i>=0; i--) {
            for (int j=0; j<8; j++) {
                if (map[i][j] == '#') {
                    map[i][j] = '.';
                    if (i != 7) {
                        map[i+1][j] = '#';
                    }
                }
            }
        }
    }

    boolean foundWall() {
        for (int i=0; i<8; i++) {
            for (int j=0; j<8; j++) {
                if (map[i][j] == '#')
                    return true;
            }
        }
        return false;
    }

    void printMap() {
        for (int i=0; i<8; i++) {
            for (int j=0; j<8; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("---------------");
    }

    void BFS() {
        Queue<Node> Q = new LinkedList<>();
        Q.add(new Node(7, 0)); // 시작점 큐에 넣기
        while(!Q.isEmpty()) {
            // ★ 한 턴이 끝날 때마다 방문배열은 초기화한다.벽이 움직여서 새로운 경로가 생길 수 있기 때문
            visited = new boolean[8][8]; 
             // ★ 현재 큐에 있는 size 만큼만 꺼내서 탐색을 한다.(큐에 있던 경로 탐색완료 = 1초 경과)
            int size = Q.size();           
            for (int t=0; t<size; t++) {
                Node now = Q.poll();
                //System.out.println("Queue: poll("+now.x+", "+now.y+") : count = "+count);
                // 그 위치에 벽이 있으면 탐색 패스
                if (map[now.x][now.y] == '#') continue;
                // 맵에 벽이 없으면 종료
                if (!foundWall()) {
                    System.out.println(1);
                    return;
                }
                //도착지 도착하면 종료
                if (now.x == 0 && now.y == 7) {
                    System.out.println(1);
                    return;
                }
                // 9개 방향으로 캐릭터 이동
                for (int i=0; i<9; i++) {
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];
                    // 가지치기
                    if (nx<0 || nx>=8 || ny<0 || ny>=8) continue; // 맵 범위 벗어나면 패스
                    if (map[nx][ny] == '#') continue; // 벽을 만나면 패스
                    if (visited[nx][ny]) continue; // 방문한 곳이면 패스
                    // 큐에 넣기
                    Q.add(new Node(nx, ny));
                    visited[nx][ny] = true;
                    //System.out.println("Queue: add("+nx+", "+ny+")");
                }
            }
            // 벽을 아래로 이동
            moveWall();
            //printMap();
        }
        System.out.println(0);
    }

	void Solve() {
        visited = new boolean[8][8];
        BFS();
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        map = new char[8][8];
        for (int i=0; i<8; i++) {
            String str = br.readLine();
            for (int j=0; j<8; j++) {
                map[i][j] = str.charAt(j);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}