백준 16954번 움직이는 미로 탈출

문제

나의 풀이

import java.util.*;

public class Main {
    final static int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1, 0 }; // (0, 0) 안 움직이는 경우
    final static int dy[] = { 1, -1, 0, 0, 1, 1, -1, -1, 0 };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 8;
        String a[] = new String[n];
        boolean check[][][] = new boolean[8][8][9];
        for(int i = 0; i < n; i++) {
            a[i] = sc.next();
        }
        
        Queue<Integer> q = new LinkedList<>();
        q.add(7); q.add(0); q.add(0); // 시작점
        check[7][0][0] = true;
        
        boolean answer = false;
        while(!q.isEmpty()) {
            int x = q.poll();
            int y = q.poll();
            int t = q.poll();
            if(x == 0 && y == 7) { // 도착점인 경우
                answer = true;
            }
            for(int k = 0; k < 9; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                int nt = Math.min(t + 1, 8); // 8초 이상으론 안되게(8초 이후는 벽이 없음)
                if(0 <= nx && nx < n && 0 <= ny && ny < n) { // 범위 안인 경우
                    if(nx - t >= 0 && a[nx - t].charAt(ny) == '#') { // 이동하기 전에 봤을 때 다음 칸이 벽인 경우
                        continue;
                    }
                    if(nx - t - 1 >= 0 && a[nx - t - 1].charAt(ny) == '#') { // 이동하고 나면 벽이 내려오는 경우
                        continue;
                    }
                    if(check[nx][ny][nt] == false) { // 아직 방문하지 않은 경우
                        check[nx][ny][nt] = true;
                        q.add(nx); q.add(ny); q.add(nt);
                    }
                }
            }
        }
        System.out.println(answer ? 1 : 0);
    }
}

몇초가 흘렀는지에 대한 정보도 가지고 있어야 한다. (r-t,c)가 1인지 0인지를 보면 t초후에 벽인지 아닌지 알 수 있다. 그 이유는 t초 후에 (r,c)로 벽이 내려왔다면 그 벽은 (r-t,c)에 있던 벽이기 때문이다.

결과

백준 3055번 탈출

문제

나의 풀이

import java.util.*;

public class Main {
    static class Pair {
        int x, y;
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int dx[] = { 1, -1, 0, 0 };
    public static int dy[] = { 0, 0, 1, -1 };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        String a[] = new String[n];
        int water[][] = new int[n][m];
        int d[][] = new int[n][m];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextLine();
            for(int j = 0; j < m; j++) {
                water[i][j] = -1;
                d[i][j] = -1;
            }
        }

        Queue<Pair> q = new LinkedList<>();
        int sx = 0, sy = 0, ex = 0, ey = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(a[i].charAt(j) == '*') { // 물인 경우
                    q.offer(new Pair(i, j));
                    water[i][j] = 0; // 0초
                } else if(a[i].charAt(j) == 'S') { // 고슴도치 위치
                    sx = i;
                    sy = j;
                } else if(a[i].charAt(j) == 'D') { // 비버 소굴 위치
                    ex = i;
                    ey = j;
                }
            }
        }

        // 물 언제 차는지 계산
        while(!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.x;
            int y = p.y;
            for(int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) { // 범위 밖인 경우
                    continue;
                }
                if(water[nx][ny] != -1) { // 이미 계산된 경우
                    continue;
                }
                if(a[nx].charAt(ny) == 'X') { // 돌인 경우
                    continue;
                }
                if(a[nx].charAt(ny) == 'D') { // 도착지인 경우
                    continue;
                }
                water[nx][ny] = water[x][y] + 1; // 시간 업데이트
                q.offer(new Pair(nx, ny));
            }
        }

        // 고슴도치 도착 가능한지 탐색
        q.offer(new Pair(sx, sy)); // 고슴도치 위치를 시작점으로
        d[sx][sy] = 0;
        while(!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.x;
            int y = p.y;
            for(int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) { // 범위 밖인 경우
                    continue;
                }
                if(d[nx][ny] != -1) { // 이미 방문한 경우
                    continue;
                }
                if(a[nx].charAt(ny) == 'X') { // 돌인 경우
                    continue;
                }
                if(water[nx][ny] != -1 && d[x][y] + 1 >= water[nx][ny]) { // 이동했을 때 물인 경우
                    continue;
                }
                d[nx][ny] = d[x][y] + 1; // 시간 업데이트
                q.offer(new Pair(nx, ny));
            }
        }

        if(d[ex][ey] == -1) { // 도착하지 못한 경우
            System.out.println("KAKTUS");
        } else {
            System.out.println(d[ex][ey]);
        }
    }
}

물이 언제 차는지 미리 구해놓은 다음 고슴도치를 그 다음 이동시킨다.

결과