[BFS] 백준 - 17836번: 공주님을 구해라! Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

17836번: 공주님을 구해라!

 

 

위 문제는 n * m의 맵에서 t 시간이 주어지는데 용사는 (0, 0) 지점에서 시작하여 t 시간 이내로 (n, m)까지 가야 한다.

근데 도중에 검을 획득하게 되면 벽을 무제한으로 뚫고 갈 수 있다.

이때 가장 빠르게 가는 시간을 구하고 못 가거나 t 시간 이내로 도착하지 못했을 경우 Fail을 반환하면 된다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] map;
    static boolean[][][] visited;
    static int n, m, t;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        visited = new boolean[2][n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                String str = st.nextToken();
                if (str.equals("1")) {
                    map[i][j] = 1;
                } else if (str.equals("2")) {
                    map[i][j] = 2;
                }
            }
        }

        int result = bfs(0, 0);

        if (result == -1) {
            System.out.println("Fail");
            return;
        }

        System.out.println(result);
    }

    private static int bfs(int startX, int startY) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{startX, startY, 0, 0});
        visited[0][startX][startY] = true;

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int x = poll[0];
            int y = poll[1];
            int s = poll[2]; //검 유무
            int c = poll[3]; //이동한 시간

            if (c > t) {
                break;
            }

            if (x == n - 1 && y == m - 1) {
                return c;
            }

            for (int i = 0; i < 4; i++) {
                int nowX = x + dx[i];
                int nowY = y + dy[i];

                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                    if (s == 0) {
                        if (map[nowX][nowY] == 0 && !visited[0][nowX][nowY]) {
                            q.add(new int[]{nowX, nowY, s, c + 1});
                            visited[0][nowX][nowY] = true;
                        } else if ((map[nowX][nowY] == 2 && !visited[0][nowX][nowY])) {
                            q.add(new int[]{nowX, nowY, s + 1, c + 1});
                            visited[0][nowX][nowY] = true;
                        }
                    } else {
                        if (!visited[1][nowX][nowY])
                            q.add(new int[]{nowX, nowY, s, c + 1});
                        visited[1][nowX][nowY] = true;
                    }
                }
            }
        }
        return -1;
    }
}

 

크게 어려울 건 없지만 벽을 뚫는 작업이 필요하기 때문에 visited를 3차원으로 생성하여 0일 때는 검을 갖고 있지 않았을 때 방문 처리를 해주고 1일 때는 검을 갖고 있을 때 방문 처리를 해주면 된다.