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

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

17836번: 공주님을 구해라!

 

풀이 방법

• 검을 습득할 시 모든 벽을 통과할 수 있다. 그 전에는 벽을 통과하지 못하므로, 두 개의 맵을 준비해야 한다.
• 하나는 검을 습득하지 못한 상태로 이동하는 맵, 다른 하나는 검을 습득한 상태에서의 맵이다. 두 개의 맵이 준비되어야 하므로 맵은 3차원 리스트 형태(배열 형태)가 되어야 할 것이다. 물론 방문 확인 배열 역시 3차원이 되어야 한다.
• 만약 검이 용사가 이동할 수 없는 곳에 존재하는 경우에는 검이 없는 상태로 이동할 수 밖에 없다.
• 또한 최단거리까지 간 시간이 주어진 시간 T보다 큰 경우에는 구조할 수 없기 때문에 Fail이 된다.

 

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Location{
    int x;
    int y;
    int z;

    Location(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

public class StudyCode {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();
        StringTokenizer st = new StringTokenizer(line);

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        int[][][] board = new int[2][N + 1][M + 1];

        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<M; j++){
                int status = Integer.parseInt(st.nextToken());
                board[0][i][j] = status;
                board[1][i][j] = status;
            }
        }

        Deque<Location> queue = new ArrayDeque<>();
        boolean[][][] visited = new boolean[2][N + 1][M + 1];
        int ans = -1;

        queue.add(new Location(0, 0, 0));
        visited[0][0][0] = true;

        while(!queue.isEmpty()){
            Location location = queue.pop();

            int y = location.y;
            int x = location.x;
            int sword = location.z;

            if(y == N - 1 && x == M - 1){
                ans = board[sword][y][x];
                break;
            }

            for(int i = 0; i<4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];

                if(ny < 0 || ny >= N || nx < 0 || nx >= M){
                    continue;
                }

                if(sword == 0 && !visited[sword][ny][nx] && board[sword][ny][nx] != 1){
                    visited[sword][ny][nx] = true;

                    if(board[sword][ny][nx] == 2){
                        board[sword + 1][ny][nx] = board[sword][y][x] + 1;
                        visited[sword + 1][ny][nx] = true;
                        queue.add(new Location(nx, ny, sword + 1));
                    }
                    else{
                        board[sword][ny][nx] = board[sword][y][x] + 1;
                        queue.add(new Location(nx, ny, sword));
                    }
                }
                else if(sword == 1 && !visited[sword][ny][nx]){
                    visited[sword][ny][nx] = true;
                    board[sword][ny][nx] = board[sword][y][x] + 1;
                    queue.add(new Location(nx,ny, sword));
                }
            }
        }

        if(ans > 0 && ans <= T){
            bw.write(String.valueOf(ans));
            bw.newLine();
        }
        else{
            bw.write("Fail\n");
        }
        bw.flush();
    }
}

• 비슷한 유형의 문제로는 벽 부수고 탈출하기가 있다.