Baekjoon 17836 공주님을 구해라! JAVA

17836번: 공주님을 구해라!

문제

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

 

조건

[입력]

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N, M)은 0이다.

 

[출력]

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

 

풀이

해당 문제는 1,1에서 N, M까지 가는 최단 이동 횟수를 구하는 문제다. 단 제한시간이 주어지며 제한 시간 안에 가지 못하면 실패하고 칼을 먹을 경우 벽을 부스고 이동할 수 있다.

 

해당 문제는 bfs를 이용하여 해결했고 검을 먹은 여부를 체크하기 위해 방문 배열을 3차원 배열을 이용하여 체크하였다.

로직은 아래와 같이 구현하였다.

 

1. 입력 처리를 한다.

2. bfs를 돌린다.

    1. 0,0을 방문 처리하고, 큐에 담는다.

    2. 큐가 빌 때까지 반복한다.

        1. 지금 위치가 칼이면 객체 값을 변경한다.

        2. 지금 위치가 도착인 경우 걸린 시간을 체크해서 리턴해준다.

        3. 4방 탐색을 실시한다

            1. 배열 범위를 벗어나면 다음 방향을 탐색한다.

            2. 칼을 먹었으면 방문 체크만 해서 큐에 담고 방문 처리한다.

            3. 칼을 먹지 않았다면 벽인지와 방문 체크만 하고 큐에 담고 방문 처리한다.

    3. 큐가 비었는데 빠져나오지 못하면 실패한 경우 -1을 리턴한다.

3. bfs 리턴 값을 ans에 저장하다.

4. ans 값이 -1 이면 Fail를 그렇지 않으면 ans를 출력한다.

 

코드

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

public class Main {

    static int N, M, T, ans ,map[][], dy[]={-1,1,0,0} , dx[]={0,0,-1,1};
    static boolean[][][] visit; // 칼을 먹은경우와 안먹은 경우 체크를 위해 3차원 배열 사용
    static Queue<Hero> queue = new LinkedList<>();

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

        map = new int[N][M];
        visit = new boolean[N][M][2]; // 0은 칼못먹었을때 1은 칼먹었을때

        for (int i = 0; i < N; i++) { // 입력처리
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        ans = bfs();
        if(ans == -1)
            System.out.println("Fail");
        else
            System.out.println(ans);
    }

    private static int bfs() {
        visit[0][0][0] = true;
        queue.add(new Hero(0,0,0,false));
        while (!queue.isEmpty()){
            Hero hero = queue.poll();
            if(map[hero.y][hero.x] == 2) // 위치가 칼일경우 객체 sword값을 변경한다.
                hero.sword = true;
            if(hero.y == N - 1 && hero.x == M - 1) { // 도착한경우 걸린시간을 체크해서 리턴해준다.
                if (hero.n <= T)
                    return hero.n;
                return -1;
            }
            for (int i = 0; i < 4; i++) {
                int ny = hero.y + dy[i];
                int nx = hero.x + dx[i];
                if(ny <0 || nx <0 || ny >= N || nx >= M) // 배열 범위를 벗어나면 건너뛴다.
                    continue;
                if(hero.sword){ // 칼을 먹은 경우
                    if(!visit[ny][nx][1]){ // 방문했는지만 체크하고 모두 큐에 담는다.
                        visit[ny][nx][1] = true;
                        queue.add(new Hero(ny,nx, hero.n+1, true));
                    }
                }else{ // 칼을 못먹은 경우
                    if(map[ny][nx] == 1 || visit[ny][nx][0]) // 벽인지와 방문했는지를 체크하고 큐에담는다.
                        continue;
                    visit[ny][nx][0] = true;
                    queue.add(new Hero(ny,nx, hero.n+1, false));
                }
            }
        }
        return -1; // 도착하지 못한경우
    }

    static class Hero{
        int y, x, n;
        boolean sword;
        Hero(int y, int x, int n, boolean sword){
            this.y = y;
            this.x = x;
            this.n = n;
            this.sword = sword;
        }
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드