[BOJ] 3055번 탈출 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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 class Pos {
        int r;
        int c;

        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int R, C, time;
    static char[][] map;
    static Queue<Pos> waterQ = new ArrayDeque<>();
    static Queue<Pos> q = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        // map 배열 입력 받으면서
        // 물, 고슴도치 위치 정보: 물 큐, 고슴도치 큐에 값 삽입
        for (int i = 0; i < R; i++) {
            String s = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == '*') waterQ.add(new Pos(i, j));
                if (map[i][j] == 'S') q.add(new Pos(i, j));
            }
        }
        // BFS 수행 결과 값에 따라 출력
        if (bfs()) System.out.println(time);
        else System.out.println("KAKTUS");
    }

    private static boolean bfs() {
        while (!q.isEmpty()) {
            time++;
            // 물 이동
            int size = waterQ.size();
            for (int s = 0; s < size; s++) {
                Pos now = waterQ.poll();
                for (int i = 0; i < 4; i++) {
                    int nr = now.r + dr[i];
                    int nc = now.c + dc[i];
                    if (isOutOfRange(nr, nc)) continue;
                    if (immovable(nr, nc, '*', 'D', 'X')) continue;
                    map[nr][nc] = '*';
                    waterQ.add(new Pos(nr, nc));
                }
            }

            // 고슴도치 이동
            size = q.size();
            for (int s = 0; s < size; s++) {
                Pos now = q.poll();
                for (int i = 0; i < 4; i++) {
                    int nr = now.r + dr[i];
                    int nc = now.c + dc[i];
                    if (isOutOfRange(nr, nc)) continue;
                    if (immovable(nr, nc, '*', 'S', 'X')) continue;
                    if (map[nr][nc] == 'D') return true;
                    map[nr][nc] = 'S';
                    q.add(new Pos(nr, nc));
                }
            }
        }
        return false;
    }

    private static boolean isOutOfRange(int nr, int nc) {
        return nr < 0 || nc < 0 || nr >= R || nc >= C;
    }

    private static boolean immovable(int nr, int nc, char c1, char c2, char c3) {
        return map[nr][nc] == c1 || map[nr][nc] == c2 || map[nr][nc] == c3;
    }
}

📄 해설

• 문제에서 제시된 조건에 따라 BFS 를 수행하면 되는 문제
• 물과 고슴도치가 개별적으로 움직이므로, 두 개의 큐를 유지한다는 아이디어가 핵심(waterQ, q)
• 지도의 정보를 입력 받으면서, 고슴도치와 물의 위치를 각각의 큐에 미리 넣음
• BFS 를 수행
  1. 고슴도치가 더 이상 이동할 수 없을때까지 반복하며, 반복마다 이동한 시간인 time 의 값을 증가시킴
  2. 큐에 들어있는 물의 개수, 고슴도치 위치의 개수 만큼만 반복문을 수행
  3. 물은 다음 위치가 물(*)이거나, 돌(X)이거나, 비버의 굴(D)이면 건너뛰고, 빈칸(.) 이거나 고슴도치(S)이면 큐에 넣고, map 의 해당 위치를 물로 표시
  4. 고슴도치는 다음 위치가 물이거나, 돌이거나, 고슴도치(이전에 있던 위치)이면 건너뛰고, 빈칸인 경우 큐에 넣고, map 의 해당 위치를 고슴도치로 표시
  5. 고슴도치 위치를 큐에 넣을 때, 다음 위치가 비버의 소굴이면 true를 반환
  6. 탐색이 다 끝나면 도착하지 못한 경우이므로 false 를 반환
• BFS 수행 결과에 따라 true 이면 time 값을 출력하고, false 이면 KAKTUS 를 출력