[백준/JAVA] 17836번: 공주님을 구해라!

📖 문제

17836번: 공주님을 구해라!

 

 

 

💡  풀이 방식

• BFS

검 존재 여부와 함께 방문 표시 나타내는 3차원 배열 visited[x][y][2]
→ visited[x][y][0] : 검 없고, 방문했음
→ visited[x][y][1] : 검 있고, 방문했음

 

(0,0)부터 (N-1, M-1)까지 BFS 탐색을 수행한다.큐에는 (현재 행 위치, 열 위치, 그람(검) 유무, 이동 시간) 4가지 값을 들고 다닌다.

Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {0, 0, 0, 0});  // 행, 열, 검 유무, 이동 시간

 

 

(0,0)에서부터 T 시간보다 작고, 공주가 있는 지점이 아닌 지점에 대해 4방향 탐색한다.

if(t > T)
    break;
if(x == N-1 && y == M-1)
    return t;

 

 

이 때 그람의 존재 유무에 따라 조건을 나눠준다.

- 그람이 존재하지 않는 경우

  ㄴ 방문한 적 없는 빈 공간(0)이라면, 해당 좌표를 방문 처리하고, 시간을 1 증가시킨 채 다음 칸으로 이동한다.

  ㄴ 방문한 적 없는 그람(2)이라면, 해당 좌표를 방문 처리하고, 시간을 1 증가시키고, 그람 존재 여부도 1로 업데이트한 후 다음 칸으로 이동한다.

if(s == 0) {	// s: 현재 칸에서의 그람 존재 여부 (0이면 존재 안 함)
    if(visited[nx][ny][0])  continue;

    if(map[nx][ny] == 0) {
        visited[nx][ny][0] = true;
        q.add(new int[] {nx, ny, s, t + 1});
    }
    else if(map[nx][ny] == 2) {	//
        visited[nx][ny][0] = true;
        q.add(new int[] {nx, ny, s + 1, t + 1});
    }
}

 

- 그람이 존재하는 경우

  ㄴ 방문한 적 없다면, 방문 처리하고, 시간을 1 증가시킨 채 다음 칸으로 이동한다.

  ㄴ 방문한적 있다면, 큐에 추가하지는 않는다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M,T;
    static int[][] map;
    static boolean[][][] visited;
    
    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];
        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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int result = bfs();        
        System.out.println(result == -1 ? "Fail" : result);
    }
    
    private static int bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {0, 0, 0, 0});  // 행, 열, 그람(검) 유무, 이동 시간
        
        visited[0][0][0] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            int s = now[2];
            int t = now[3];
            
            if(t > T)    // T시간 이내 구출할 수 없다면 Fail
                break;
            if(x == N-1 && y == M-1)    // 공주에게 도달한 경우
                return t;
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if(nx < 0 || nx >= N || ny < 0 || ny >= M)  continue;
 
                if(s == 0) {    // 그람이 존재하지 않는 경우
                    if(visited[nx][ny][0])  continue;
                    
                    if(map[nx][ny] == 0) {
                        visited[nx][ny][0] = true;
                        q.add(new int[] {nx, ny, s, t + 1});
                    }
                    else if(map[nx][ny] == 2) { // 그람 존재 확인!
                        visited[nx][ny][0] = true;
                        q.add(new int[] {nx, ny, s + 1, t + 1}); // 💥 변수 s에 그람 존재 나타내기 !
                    }
                }
                else {    // 그람이 존재하는 경우
                    if(!visited[nx][ny][1])
                        q.add(new int[]{nx, ny, s, t + 1});
                    visited[nx][ny][1] = true;
                }
            }
        }
        
        return -1;    // 도착하지 못하면 -1
    }
}
 

 

 

 

---

💦 어려웠던 점

- 방문 배열에서 3차원 배열로 명검 존재 여부 판단해서 사용할 생각은 했는데, 조건을 잘못나눠서 정답이 잘못 나왔다.

- 처음에 검이 있는 좌표를 구해서 (0,0)~검이 있는 좌표까지의 거리 + 검이 있는 좌표~공주 위치까지의 거리를 합한 값과 그냥 (0,0)부터 (N-1,M-1)까지 bfs로 최단거리를 구한 값을 구해 두 값을 비교해 더 작은 값을 정답으로 출력하려고 했었다. (그런 풀이도 찾긴 했는데... 위의 풀이가 나한테 더 맞아서 위의 풀이로 제출함)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BFS] 백준 - 17836번: 공주님을 구해라! Java 풀이