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

📌 문제

알고리즘 분류 : 그래프
난이도 : 골드5
출처 : 백준 - 공주님을 구해라!

🦧 문제 풀이 접근

최단거리 측정 문제이므로 BFS를 사용한다. 이때 그람을 찾았을 경우, 못찾았을 경우 2가지의 경우를 나눠서 BFS를 한다. 즉 visited 배열을 2차원이 아닌 3차원 배열로 선언하여 0은 그람을 찾지 못한 경우, 1은 찾은 경우로 나눠서 BFS를 한다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        int board[][] = new int[N][M];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        boolean visited[][][] = new boolean[N][M][2];//0은 노그람, 1은 그람
        Queue<Node> q = new LinkedList<>();
        int di[] = {0,1,0,-1};
        int dj[] = {1,0,-1,0};
        q.offer(new Node(0,0,0,false));
        visited[0][0][0] = true;
        while(!q.isEmpty()) {
            Node current = q.poll();
            if(current.count>T) break;
            if(current.i==N-1 && current.j==M-1) {
                System.out.println(current.count);
                return;
            }
            for(int i=0;i<4;i++) {
                int ci = current.i+di[i];
                int cj = current.j+dj[i];

                if(0<=ci && ci<N && 0<=cj && cj<M) {
                    if(!current.isGram) {
                        if(!visited[ci][cj][0] && board[ci][cj] == 0) {
                            q.offer(new Node(ci,cj, current.count+1,false ));
                            visited[ci][cj][0]=true;
                        }
                        else if(!visited[ci][cj][0] && board[ci][cj] == 2) {
                            q.offer(new Node(ci,cj, current.count+1,true ));
                            visited[ci][cj][0] = true;
                        }
                    }
                    else {
                        if(!visited[ci][cj][1]) {
                            q.offer(new Node(ci,cj,current.count+1,true));
                            visited[ci][cj][1] = true;
                        }

                    }
                }
            }


        }
        System.out.println("Fail");
    }
}
class Node {
    int i;
    int j;
    int count;
    boolean isGram;
    Node(int i, int j, int count, boolean isGram) {
        this.i = i;
        this.j = j;
        this.count = count;
        this.isGram = isGram;
    }
}

🥇 결과

🎓 느낀점

기존에 BFS에서 벽을 부시는 조건이 추가되니 난이도가 어려워졌다. 비슷한 유형의 문제를 많이 풀어봐야겠다.