본문 바로가기
알고리즘 문제

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

by Lpromotion 2024. 9. 30.

1. 문제설명

용사는 (N, M) 크기의 성 입구 (1, 1)로 들어왔다. 성의 여러 군데는 마법 벽이 세워져있고, 용사는 마법 벽을 통과할 수 없다. 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야 한다.

저주에 걸린 공주는 T시간 이내에 용사를 만나지 못하면 돌로 변하게 된다. 용사는 한 칸을 이동하는 데 한 시간이 걸리고, 상하좌우로 이동할 수 있다.

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

용사가 공주님을 안전하게 구출할 수 있는지, 얼마나 빨리 구할 수 있는지 구하는 문제이다.

  • 시간 제한: 1초
  • 메모리 제한: 256MB

 

2. 접근 방식

  • BFS 를 사용하여 (N, M)까지 도달하는 최소 시간을 구한다.
  • 그람을 찾은 경우와 찾지 못한 경우를 3차원 방문 배열을 사용해 구분하여 처리한다.
  • Node 클래스를 사용해 현재 위치, 그람 소지 여부, 걸린 시간을 함께 저장한다.
  • 이동 경우
    • 이전에 그람을 찾지 못한 경우
      • 이전에 방문한 적 없고, 빈 공간일 경우 이동
      • 이전에 방문한 적 없고, 그람이 있을 경우 그람 서부 여부 체크하고 이동
    • 이전에 그람을 찾은 경우
      • 이전에 방문한 적 없는 경우 이동
  • 도착점에 도달하면 걸린 시간의 최소값을 갱신한다.
  • 구한 최소 시간이 T 시간 이내이면 도달한 최소 시간을 출력하고, 아닌 경우에는 “Fail”을 출력한다.

 

3. 최종 코드

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

public class Main {
    static int n, m; // 성의 가로, 세로 길이
    static int t; // 제한 시간
    static int[][] map; // 성의 공간 정보 저장
    static int resultTime; // 최종 걸린 시간

    // 방향 배열 (상하좌우)
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static class Node {
        int x, y;
        boolean findGram; // 그람 찾았는지 여부
        int time; // 걸린 시간

        public Node(int x, int y, boolean findGram, int time) {
            this.x = x;
            this.y = y;
            this.findGram = findGram;
            this.time = time;
        }
    }

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

        map = new int[n][m];
        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());
            }
        }

        resultTime = t+1;
        bfs(0, 0);

        if(resultTime == 0 || resultTime > t) System.out.println("Fail");
        else System.out.println(resultTime);
    }

    static void bfs(int x, int y) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(x, y,  false, 0));
        boolean[][][] visited = new boolean[n][m][2]; // 그람을 찾지 못한 경우, 찾은 경우로 나눔
        visited[x][y][0] = true;
        
        while(!q.isEmpty()) {
            Node c = q.poll(); // 현재 위치 꺼내기

            if(c.x == n-1 &&  c.y == m-1) { // 도착점에 도달하면
                // 걸린 시간 최소값 갱신
                System.out.println(c.time);
                resultTime = Math.min(resultTime, c.time);
                continue;
            }
            
            for(int i=0; i<4; i++) { // 상하좌우 탐색
                int nx = dx[i] + c.x;
                int ny = dy[i] + c.y;
                
                // 다음 위치가 성의 범위 내에 있는 경우
                if(nx>=0 && nx<n && ny>=0 && ny<m) {
                    if(!c.findGram) { // 이전에 그람을 찾지 못한 경우
                        if(!visited[nx][ny][0] && map[nx][ny] == 0) {
                            // 이전에 방문한 적 없고, 빈 공간일 경우 이동
                            visited[nx][ny][0] = true;
                            q.add(new Node(nx, ny, c.findGram, c.time+1));
                        } else if(!visited[nx][ny][0] && map[nx][ny] == 2) {
                            // 이전에 방문한 적 없고, 그람이 있을 경우 그람 여부 체크하고 이동
                            visited[nx][ny][0] = true;
                            q.add(new Node(nx, ny, true, c.time+1));
                        }
                    } else { // 이전에 그람을 찾은 경우
                        if(!visited[nx][ny][1]) {
                            // 이전에 방문한 적 없는 경우 이동
                            visited[nx][ny][1] = true;
                            q.add(new Node(nx, ny, c.findGram, c.time+1));
                        }
                    }
                }
            }
        }
    }
}
반응형

댓글