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

17836번: 공주님을 구해라!

---

[BFS]

우리는 생각해야한다. '그람'을 얻었을 때와 얻지 않았을 때의 visit를. 즉 visit는 3차원 배열로 선언했다. 이동한 횟수 move 또한 3차원 배열로 만들 수 있으나, 그냥 Queue의 원소로 넘겨주었다. 따라서 Queue의 원소에 들어가는 값은 총 4가지이다.

    static class Point{
        int y, x, find, move;
        
        public Point(int yy, int xx, int find, int move){
            y=yy;
            x=xx; 
            this.find = find; 
            this.move = move;
        }
    }
    //y x : 좌표
    //find : 그람 습득 여부 (0이면 없을 때, 1이면 있을 때
    //move : 이동횟수

맵의 값 중 '2'를 만났을 때 부터 벽을 마음껏 뚫을 수 있다.

 

그리고 다음 정점을 방문할 수 있는지에 대한 조건이 까다로우니 잘 짚고 넘어가자.

//좌표가 범위를 벗어날 때
//이미 방문한 정점
//이동 횟수가 k를 넘을 때
//그람이 없으며 벽(1)을 만났을 때
if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx][find] || nMove > t) continue;

if(find == 0 && map[ny][nx] == 1) continue;

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Point{
        int y, x, find, move;
        public Point(int yy, int xx, int find, int move){
            y=yy; x=xx; this.find = find; this.move = move;
        }
    }
    static int r,c,t;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int[][] map = new int[101][101];
    static boolean[][][] visit = new boolean[101][101][2];

    static int BFS(){

        Queue<Point> Q = new LinkedList<>();
        int result = 100000000;
        visit[1][1][0] = true;

        Q.add(new Point(1,1, 0, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int move = p.move;
            int find = p.find;

            if(y == r && x == c)
                result = Math.min(result, move);

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];
                int nMove = move + 1;

                if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx][find] || nMove > t) continue;
                if(find == 0 && map[ny][nx] == 1) continue;

                visit[ny][nx][find] = true;
                Q.add(new Point(ny, nx, find, nMove));

                if(map[ny][nx] == 2){
                    visit[ny][nx][1] = true;
                    Q.add(new Point(ny, nx, 1, nMove));
                }
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        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());

        for(int i=1; i<=r; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=c; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        int result = BFS();
        System.out.println(result != 100000000? result : "Fail");
    }
}