[백준]17836: 공주님을 구해라! - JAVA

[백준]17836: 공주님을 구해라!

17836번: 공주님을 구해라!

풀이

탐색을 하면서 최단 경로를 찾되, 그람의 유무에 따라 경로가 달라질 수 있으므로 그람의 유무에 나눠 탐색을 진행하면 되는 문제이다. 최단 시간을 요구하므로 BFS탐색을 활용하였다.

 

이 문제에서 경로를 탐색할 때 필요한 값은 다음과 같다.

• X좌표, Y좌표, 현재 탐색 깊이, 그람의 유무

해당 정보들을 클래스로 만들어 주었다.

 

탐색을 하는 중에는, 그람의 유무에 따라 작업을 나눠주었다.

🔹 그람이 없을때

이동할 노드를 방문한 적이 없으며, 보드의 값이 0일때만 지나갈 수 있다. 보드 값이 2라면 그람을 획득한 것이므로 그람의 유무를 true로 변경해 주고 탐색을 진행한다.

 

🔹 그람이 있을때

보드의 값과 상관없이 이동할 노드를 방문하적 없다면 이동할 수 있다. 

 

코드

import java.util.*;
 
public class Main {
 
    static int n, m, t;
    static int[][] board;
    static boolean[][][] visited;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        t = scan.nextInt();
        
        board = new int[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = scan.nextInt();
            }
        }
 
        visited = new boolean[n][m][2];// 0은 그람이 없을때, 1은 그람이 있을때
        int result = bfs(0, 0);
        if(result == -1) System.out.println("Fail");
        else System.out.println(result);
    }
 
    public static int bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y, 0, false));
        visited[x][y][0] = true;
 
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            if(current.count > t) break;
            if(current.x == n - 1 && current.y == m - 1) return current.count;
 
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if(!current.isGram) { //그람 없음
                        if(!visited[nx][ny][0] && board[nx][ny] == 0) {
                            q.offer(new Node(nx, ny, current.count + 1, current.isGram));
                            visited[nx][ny][0] = true;
                        } else if(!visited[nx][ny][0] && board[nx][ny] == 2) {
                            q.offer(new Node(nx, ny, current.count + 1, true));
                            visited[nx][ny][0] = true;
                        }
                    } else { //그람 있음
                        if(!visited[nx][ny][1]) {
                            q.offer(new Node(nx, ny, current.count + 1, current.isGram));
                            visited[nx][ny][1] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
 
    public static class Node {
        int x;
        int y;
        int count;
        boolean isGram;
 
        public Node(int x, int y, int count, boolean isGram) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.isGram = isGram;
        }
    }
}