백준 17836. 공주님을 구해라!

문제

17836번: 공주님을 구해라!

---

 

문제풀이

---

 모든 경로를 탐색 하면서, 그람의 유무에 따라 경로가 달라질 수 있으므로 두가지 경우를 생각해서 BFS탐색을 사용해 풀었다.

Node라는 클래스는 행, 열, 탐색한 시간, 그람의 유무를 가지고 클래스로 만들었다.

방문체크는 3차원 배열 visited를 사용하였고, visited[r][c][0]은 그람을 가지고 있지 않았을 때, visited[r][c][1]은 그람을 가지고 있을 때 방문체크를 나누어서 했다.

 

탐색시 두가지 경우의 수를 나눠 진행

· 그람이 있을 때

  용사는 벽이 있던 비어있던 어디든 갈수 있어 방문한 적이 없으면 탐색한다.

· 그람이 없을 때

  이동할 곳을 방문한 적이 없으며, 벽이 아닐 경우 탐색 할 수 있다. 

  값이 2라면 그람을 획든한 것이므로 그람을 true로 변경하고 탐색을 진행한다.

 

소스코드(Java)

package baek;

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

/**
 * 공주님을 구해라!
 * https://www.acmicpc.net/problem/17836
 */
public class baek17836 {
    static class Node {
        int r, c, d;
        boolean key;

        public Node(int r, int c, int d, boolean key) {
            this.r = r;
            this.c = c;
            this.d = d;
            this.key = key;
        }
    }

    static int R, C, T;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int[][] map;
    static boolean[][][] visited;

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        map = new int[R][C];
        visited = new boolean[R][C][2];

        for (int r = 0; r < R; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }


        int answer = bfs(new Node(0, 0, 0, false));
        if (answer == -1) {
            System.out.println("Fail");
        } else {
            System.out.println(answer);
        }
    }

    static int bfs(Node start) {
        Queue<Node> q = new LinkedList<>();
        q.offer(start);
        visited[start.r][start.c][0] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur.d > T) {
                break;
            }
            if (cur.r == R - 1 && cur.c == C - 1) {
                return cur.d;
            }

            for (int d = 0; d < 4; d++) {
                int nr = cur.r + dr[d];
                int nc = cur.c + dc[d];

                if (!isIn(nr, nc)) {
                    continue;
                }
                if (cur.key) {
                    if (visited[nr][nc][1]) {
                        continue;
                    }
                    q.offer(new Node(nr, nc, cur.d + 1, true));
                    visited[nr][nc][1] = true;
                } else {
                    if (visited[nr][nc][0]) {
                        continue;
                    }
                    if (map[nr][nc] == 1) {
                        continue;
                    }

                    if (map[nr][nc] == 0) {
                        q.offer(new Node(nr, nc, cur.d + 1, false));
                    } else {
                        q.offer(new Node(nr, nc, cur.d + 1, true));
                    }
                    visited[nr][nc][0] = true;
                }
            }
        }
        return -1;
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && c >= 0 && r < R && c < C;
    }
}