[백준] 17836번 : 공주님을 구해라! - 자바[Java]

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

17836번: 공주님을 구해라!

풀이

BFS를 사용해서 출발지부터 목적지까지의 최단거리를 구하면 된다.

최단거리를 총 2번 구하는데, 검을 얻지 않는 상태와 검을 얻은 상태의 최단거리를 구하여 비교한다.

둘 중 더 작은 최단거리가 T보다 작거나 같다면 그 값을 출력하고, 그렇지 않다면 Fail을 출력한다.

 

int bfs(int startR, int startC, int destR, int destC): (startR, startC)를 출발점으로 하고 (destR, destC)를 도착점으로 할 때의 최단거리를 구한다.

static int bfs(int startR, int startC, int destR, int destC) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{startR, startC});
        boolean[][] visited = new boolean[n][m];
        visited[startR][startC] = true;

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();
                int r = cur[0];
                int c = cur[1];

                if (r == destR && c == destC) {
                    return cnt;
                }

                for (int k = 0; k < 4; k++) {
                    int nr = r + dx[k];
                    int nc = c + dy[k];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && map[nr][nc] != 1) {
                        q.add(new int[]{nr, nc});
                        visited[nr][nc] = true;
                    }
                }
            }
            cnt++;
        }

        return -1;
    }

 

int swordBfs(int startR, int startC, int destR, int destC): 검을 얻은 상태에서 (startR, startC)를 출발점으로 하고 (destR, destC)를 도착점으로 할 때의 최단거리를 구한다.

static int swordBfs(int startR, int startC, int destR, int destC) {
        ...

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                ...

                for (int k = 0; k < 4; k++) {
                    ...
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc]) { // 이 부분만 다르다.
                        q.add(new int[]{nr, nc});
                        visited[nr][nc] = true;
                    }
                }
            }
            cnt++;
        }

        return -1;
    }

 

코드

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

public class Main {

    static int n, m;
    static int swordR, swordC;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    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());
        int t = Integer.parseInt(st.nextToken());

        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) {
                    swordR = i;
                    swordC = j;
                }
            }
        }

        int minDist = 10001;
        int noSwordMinDist = bfs(0, 0, n-1, m-1);
        if (noSwordMinDist != -1) {
            minDist = Math.min(minDist, noSwordMinDist);
        }

        int swordMinDist = bfs(0, 0, swordR, swordC);

        if (swordMinDist != -1) {
            int swordToDestDist = swordBfs(swordR, swordC, n-1, m-1);
            if (swordToDestDist != -1) {
                minDist = Math.min(minDist, swordMinDist + swordToDestDist);
            }
        }

        if (minDist <= t) {
            System.out.println(minDist);
        } else {
            System.out.println("Fail");
        }
    }

    static int bfs(int startR, int startC, int destR, int destC) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{startR, startC});
        boolean[][] visited = new boolean[n][m];
        visited[startR][startC] = true;

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();
                int r = cur[0];
                int c = cur[1];

                if (r == destR && c == destC) {
                    return cnt;
                }

                for (int k = 0; k < 4; k++) {
                    int nr = r + dx[k];
                    int nc = c + dy[k];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && map[nr][nc] != 1) {
                        q.add(new int[]{nr, nc});
                        visited[nr][nc] = true;
                    }
                }
            }
            cnt++;
        }

        return -1;
    }

    static int swordBfs(int startR, int startC, int destR, int destC) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{startR, startC});
        boolean[][] visited = new boolean[n][m];
        visited[startR][startC] = true;

        int cnt = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cur = q.poll();
                int r = cur[0];
                int c = cur[1];

                if (r == destR && c == destC) {
                    return cnt;
                }

                for (int k = 0; k < 4; k++) {
                    int nr = r + dx[k];
                    int nc = c + dy[k];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc]) {
                        q.add(new int[]{nr, nc});
                        visited[nr][nc] = true;
                    }
                }
            }
            cnt++;
        }

        return -1;
    }
}

 

다른 풀이

위의 풀이와 다르게 한 번의 BFS로 최단거리를 구한다.

Data 클래스를 생성하여 (r, c, 시간, 검의 유무)를 저장하고 BFS 수행 시 Queue<Data> q를 생성한다.

주의할 점은, 방문배열을 2차원으로 사용하게 되면 검을 주운 이후에 앞지르는 경우를 고려할 수 없기 때문에, 검이 있을때와 없을 때를 구분하여 방문배열을 생성해야 한다.

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

public class Main {

    static class Data {
        int r, c, t;
        boolean isSword;

        public Data(int r, int c, int t, boolean isSword) {
            this.r = r;
            this.c = c;
            this.t = t;
            this.isSword = isSword;
        }
    }

    static int n, m;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    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());
        int t = Integer.parseInt(st.nextToken());

        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int minDist = bfs();

        if (minDist != -1 && minDist <= t) {
            System.out.println(minDist);
        } else {
            System.out.println("Fail");
        }
    }

    static int bfs() {
        Queue<Data> q = new ArrayDeque<>();
        q.add(new Data(0, 0, 0, false));

        // 검을 주운 이후에 앞지르는 경우를 고려하기 위해, 검이 있을때와 없을 때를 구분하여 방문배열 생성
        boolean[][][] visited = new boolean[n][m][2];
        visited[0][0][0] = true;

        while (!q.isEmpty()) {
            Data cur = q.poll();
            int r = cur.r;
            int c = cur.c;

            if (r == n-1 && c == m-1) {
                return cur.t;
            }

            for (int k = 0; k < 4; k++) {
                int nr = r + dx[k];
                int nc = c + dy[k];
                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    if (cur.isSword) { // 검이 있는 경우
                        // 방문하지 않았을 때
                        if (!visited[nr][nc][1]) {
                            q.add(new Data(nr, nc, cur.t+1, true));
                            visited[nr][nc][1] = true;
                        }
                    }
                    else { // 검이 없는 경우
                        // 방문하지도 않고 막히지도 않았을 때
                        if (!visited[nr][nc][0] && map[nr][nc] != 1) {
                            boolean isSword = false;
                            if (map[nr][nc] == 2) {
                                isSword = true;
                            }
                            q.add(new Data(nr, nc, cur.t+1, isSword));
                            visited[nr][nc][0] = true;
                        }
                    }
                }
            }
        }

        return -1;
    }
}

참고

백준 17836 공주님을 구해라! (Java,자바)

 

위가 다른 풀이, 아래가 처음 풀었던 풀이다. 코드 길이만 차이가 나고 메모리와 시간은 근소하게 감소하였다. 다른 풀이에서 BFS를 한 번만 수행하는 것처럼 보이지만, 방문 배열 visited[][][1]에서 새롭게 BFS를 하는 것과 같으므로 처음의 풀이와 수행 시간이 크게 다르지는 않는 것 같다.

 

다른 풀이2

[백준] 17836번 - 공주님을 구하라! (java)

검을 찾으면 도착지까지 무조건 도달할 수 있기 때문에, BFS를 수행하던 중 검을 찾으면 검으로부터 도착지까지 거리(도착지의 행 - 검의 행 + 도착지의 열 - 검의 열)를 계산해 업데이트 한다.
그 후, 도착지에 도달했을 때의 시간과 검을 찾고 곧바로 가는 시간 중 더 작은 값을 출력한다.