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

문제

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

17836번: 공주님을 구해라!

 

입력

 

출력

---

알고리즘

너비 우선 탐색(BFS)

 

일단, 최단 시간을 물어봤으므로 항상 최단경로를 보장하는 BFS로 무조건 풀어야 한다. DFS로는 이 문제를 풀 수 없다.

 

그람을 구해서 벽을 부수고 가는 것이 최단경로일 수도 있고, 그람을 안구하고 돌아서 가는 것이 최선일 수도 있다. 또한, 사방이 벽으로 막혀 있어 반드시 그람을 구하고 가야되는 경우도 존재한다. 따라서, 그람을 구하고 가는 경우랑 그람을 구하지 않는 경우를 따로따로 생각해주고 방문처리를 해줘야 한다. (그람을 구한 세계와 그람을 구하지 못한 세계는 서로 다른 세계이기 때문이다.)

문제에서 예시로 나온 그림인데, 위 그림처럼 그람을 구하고 공주님에게 가는 것이 더 효율적일 수 있다.

 

따라서, 3차원 배열의 visited 배열을 만들어 방문처리를 해준다. visted[n][m][2] 이런식으로 말이다. 하나는 그람을 구하지 못한 세계를 위한 nxm짜리 방문처리 배열이고, 나머지 하나는 그람을 구한 nxm짜리 방문처리 배열이다. 참고로, 해당 코드에는 제일 작은걸 뒤에 두었지만, 가장 큰 길이의 차원을 가장 오른쪽에 놓는 것이 훨씬 좋다. 이에 대한 이유는 아래 글을 참고해주길 바란다.

 

https://www.acmicpc.net/board/view/111938

글 읽기 - 로직은 확실히 맞는데 시간초과/메모리초과가 난다면

 

그 다음, 이제 단순 BFS를 돌리면서 그람을 얻었을 경우랑 얻지 못했을 경우 분기 처리를 제대로 해주고, 공주님이 있는 칸에 도달하면 그때 시간을 반환해주고, 시간을 초과했다면 -1을 반환해주도록 코드를 짜면 답이 나온다. 이때, 중요한 것은 그람에 있는 칸에 도달했다면 반드시 그람을 집고 가는 것이 유리하다는 것이다. 그람에 있는 칸에 도달했는데 벽을 부수면 최단경로가 될 가능성이 높아지는데 밑져야 본전아닌가?

 

sword가 그람의 소지 여부를 뜻하는 것인데, 위와 같이 그람을 소지했을 때는 벽이나 빈칸을 통과할 수 있도록하고, 그람을 소지하지 않았을때는 빈칸이나 그람이 있는 칸으로만 이동할 수 있도록 분기 처리를 해주면 된다. 사실 그람을 소지한 시점에서 빈칸인지 벽인지 확인하는 부분은 별로 의미가 없다. 그람은 무조건 1개만 존재하고, 그람을 구했다면 어떤 칸이던지 갈 수 있기 때문이다. 그래도 이해를 돕고자 넣어봤다.

 

또한, 초기위치부터 그람이 있을 수도 있기 때문에 초기 큐에 집어넣을때, 그람이 있으면 바로 집고 가는게 유리하니 이 부분을 처리해줘야 할 것 같은데, 이 문제는 그걸 고려안해도 그냥 정답처리가 되는 것 같다. 그래도, 초기 위치에 그람이 있으면 반드시 집고가도록 처리해주는게 맞는 것 같다.

---

코드

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

public class Main {
    public static class Position{
        int x,y,time;
        boolean sword;

        public Position(int x, int y, int time , boolean sword){
            this.x = x;
            this.y = y;
            this.time = time;
            this.sword = sword;
        }
    }
    static int n,m,t;
    static int[] dirx = {1,-1,0,0};
    static int[] diry = {0,0,1,-1};
    static boolean[][][] visited;
    static int[][] board;
    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());
        t = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        visited = new boolean[n][m][2];

        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());
            }
        }

        int time = bfs();
        System.out.println(time != -1 ? time : "Fail");
    }

    public static int bfs(){
        Queue<Position> queue = new LinkedList<>();
        //만약 초기위치부터 그람이 있을 수도 있기 때문에 그걸 고려해줘서 넣어줘야 한다.
        //그람에 있는 칸에 도달했다면 무조건적으로 그람을 들고가는게 유리하다.
        //다만, 이 문제는 그걸 고려안해줘도 정답처리가 되는 것 같다.
        queue.add(new Position(0,0, 0, board[0][0] == 2 ? true : false ));
        visited[0][0][board[0][0] == 2 ? 1 : 0] = true;

        while(!queue.isEmpty()){
            Position position = queue.poll();
            int x = position.x;
            int y = position.y;
            int time = position.time;
            boolean sword = position.sword;
            //시간내에 도착하지 못하는 경우
            if(time>t) break;
            //공주님에게 도착하는 경우
            if(x == n-1 && y == m-1) return time;

            for(int i = 0; i<4; i++){
                int nx = x + dirx[i];
                int ny = y + diry[i];
                //범위 벗어나는지 체크
                if(nx<n && ny<m && nx>=0 && ny>=0){
                    //현재 그람이 없을 경우
                    if(!sword && !visited[nx][ny][0] && (board[nx][ny] == 0 || board[nx][ny] == 2)){
                        //그람 없는 칸으로 이동
                        if(board[nx][ny] == 0) visited[nx][ny][0] = true;
                        //이동하는 칸에 그람이 있는 경우
                        if(board[nx][ny] == 2) visited[nx][ny][1] = true;
                        //그람에 있는 칸에 도달했다면 무조건적으로 그람을 들고가는게 유리하므로 무조건 들고가는 처리를 해준다.
                        queue.add(new Position(nx, ny, time+1, board[nx][ny] == 2 ? true : false));
                    }
                    //현재 그람이 있을 경우 벽을 부술 수 있다
                    else if(sword && !visited[nx][ny][1] && (board[nx][ny] == 0 || board[nx][ny] == 1)){
                        visited[nx][ny][1] = true;
                        queue.add(new Position(nx, ny, time+1, true));
                    }
                }
            }
        }
        //시간내에 도달하지 못하는 경우
        return -1;
    }
}

---

참고

벽 부수고 이동하기 시리즈랑 거의 완전히 동일한 문제이다.

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

2206번: 벽 부수고 이동하기

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

14442번: 벽 부수고 이동하기 2

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

16933번: 벽 부수고 이동하기 3

 

다만, 벽 부수고 이동하기는 여기에 사소한 조건이 조금 더 추가되는 것 뿐인데... 왜 이것들은 골드3, 골드3, 골드 1인데 얘는 골드 5인지 잘 모르겠다.