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

 

 

 

문제 출저

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

17836번: 공주님을 구해라!

 

 

 

문제 풀이

높이 n, 너비 m인 성에서 T 시간 안에 용사가 공주를 찾을 수 있는지 확인하는 문제입니다. 

용사는 (1,1) 에서 시작하고 공주는 (n,m) 에 있습니다. 

성은 0은 통로, 1은 벽, 2는 그람을 의미합니다. 그람을 획득하면 벽을 부수면서 통과할 수 있습니다. 

 

BFS와 메모리제이션을 이용하여 풀었습니다. 

프로그래밍에서 배열의 시작은 0 입니다. BFS를 통해서 (0,0) 부터 탐색을 진행했습니다. 

3차원 int 배열 int[][][] visited = new int[n][m][2]; 을 이용해 시간을 메모리제이션 했습니다. (n : y 위치, m : x 위치, 2 : gram 획득 여부, 없으면 0, 있으면 1) 

메모리제이션을 통해 visited[n-1][m-1][0], visited[n-1][m-1][1]을 비교하여 더 작은 값을 구합니다. 이 값이 초기값이나 T 보다 크면 Fail을 출력하고 그렇지 않다면 정답으로 출력합니다. 

 

 

 

소스 코드

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

/*
공주님을 구해라
https://www.acmicpc.net/problem/17836

1% 시간 초과
DFS로 풀어서 시간 초과가 발생했다.
BFS로 바꾸어서 해결했다.
 */

public class Main {

    static int n;
    static int m;
    static int t;
    static int[][] board;
    static int[][][] visited;

    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int answer;

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

        visited = new int[n][m][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < 2; k++) {
                    visited[i][j][k] = n * m * 4;
                }
            }
        }


        Queue<Dot> que = new LinkedList<>();
        visited[0][0][0] = 0;
        que.add(new Dot(0, 0, 0, 0));



        while (!que.isEmpty()) {
            Dot d = que.poll();

            // System.out.println(d.y + " " + d.x + " " + d.time + " " + d.gram);

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

                if (check(ny, nx, d.gram)) {

                    if (visited[ny][nx][d.gram] > d.time + 1) {
                        visited[ny][nx][d.gram] = d.time + 1;

                        if (board[ny][nx] == 2) {
                            que.add(new Dot(ny, nx, d.time+1, 1));
                        }
                        else {
                            que.add(new Dot(ny, nx, d.time+1, d.gram));
                        }
                    }
                }
            }
        }

//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                System.out.print(visited[i][j][0] + " ");
//            }
//            System.out.println();
//        }
//
//        System.out.println();
//
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                System.out.print(visited[i][j][1] + " ");
//            }
//            System.out.println();
//        }



        answer = Math.min(visited[n-1][m-1][0], visited[n-1][m-1][1]);

        if (answer > t) {
            System.out.println("Fail");
            return;
        }

        if(answer == n * m * 4 ) {
            System.out.println("Fail");
        }
        else {
            System.out.println(answer);
        }



    }



    public static boolean check(int y, int x, int gram) {
        if (y >= 0 && y < n && x >= 0 && x < m) {

            if (gram == 1) {
                return true;
            }

            if (gram == 0 && board[y][x] != 1) {
                return true;
            }
        }

        return false;

    }

    public static class Dot {
        int y;
        int x;
        int time;
        int gram;

        Dot(int y, int x, int time, int gram) {
            this.y = y;
            this.x = x;
            this.time = time;
            this.gram = gram;
        }
    }



}