[BOJ] 3055 - 탈출

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/3055

3055번: 탈출

난이도: 골드 5

사용언어: JAVA

 

풀이

기본적으로는 BFS를 이용해 문제를 해결할 수 있습니다. 단지 고슴도치와 물의 위치를 모두 탐색해 주어야 하므로, 큐와 BFS 함수를 따로따로 만들어주었습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/63

[BOJ] 2178 - 미로 탐색

우선 고슴도치는 물이 같은 턴에 이동해 올 칸으로는 움직일 수 없기 때문에, 물의 이동을 먼저 체크해줍니다. 물은 빈칸이거나 고슴도치가 있는 칸으로는 옮겨갈 수 있습니다. 그 뒤에 고슴도치가 움직일 수 있는 위치를 탐색해줍니다. 고슴도치는 빈칸으로만 옮겨갈 수 있습니다. 이렇게 BFS를 반복 수행하여 고슴도치가 비버 굴에 도착할 수 있는지만 확인해주면 됩니다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
    static class position {
        int x;
        int y;
    }
 
    static Queue<position> q_w = new LinkedList<>(); // 물의 움직임을 위한 큐
    static Queue<position> q_h = new LinkedList<>(); // 고슴도치의 움직임을 위한 큐
    static char[][] arr;
    static int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 물과 고슴도치가 이동할 수 있는 방향
 
    public static void bfs_w(position p) { // 물의 움직임을 위한 bfs 함수
        int i;
        for (i = 0; i < 4; i++) {
            if (arr[p.x + d[i][0]][p.y + d[i][1]] == '.' || arr[p.x + d[i][0]][p.y + d[i][1]] == 'S') { // 빈 칸이거나 고슴도치가 있는 칸으로는 이동가능
                arr[p.x + d[i][0]][p.y + d[i][1]] = '*'; // 물이 이동한 칸은 물이 차오름
                position p1 = new position();
                p1.x = p.x + d[i][0];
                p1.y = p.y + d[i][1];
                q_w.add(p1); // 큐에 삽입
            }
        }
    }
 
    public static void bfs_h(position p) { // 고슴도치의 움직임을 위한 bfs 함수
        int i;
        for (i = 0; i < 4; i++) {
            if (arr[p.x + d[i][0]][p.y + d[i][1]] == '.' || arr[p.x + d[i][0]][p.y + d[i][1]] == 'D') { // 빈 칸이거나 비버 굴인 칸으로 이동 가능
                arr[p.x + d[i][0]][p.y + d[i][1]] = 'S'; // 중복 탐색을 막기 위해 S로 표시
                position p1 = new position();
                p1.x = p.x + d[i][0];
                p1.y = p.y + d[i][1];
                q_h.add(p1); // 큐에 삽입
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        arr = new char[R + 2][C + 2];
        int i, j, k;
        String s;
        int cnt = 0;
        position p_d = new position(); // 비버 굴의 좌표를 저장할 position 클래스
        for (i = 1; i <= R; i++) {
            s = br.readLine();
            for (j = 1; j <= C; j++) {
                arr[i][j] = s.charAt(j - 1);
                if (arr[i][j] == 'S') { // 초기의 고슴도치의 위치 큐에 삽입
                    position p = new position();
                    p.x = i;
                    p.y = j;
                    q_h.add(p);
                } else if (arr[i][j] == '*') { // 초기에 물인 칸을 큐에 삽입
                    position p = new position();
                    p.x = i;
                    p.y = j;
                    q_w.add(p);
                } else if (arr[i][j] == 'D') { // 도착지인 비버 굴의 좌표 저장
                    p_d.x = i;
                    p_d.y = j;
                }
            }
       }
 
        position p = new position();
        while (true) {
            k = q_w.size();
            for (i = 0; i < k; i++) { // 물의 움직임 체크
                p = q_w.remove();
                bfs_w(p);
            }
            k = q_h.size();
            if (k == 0) // 고슴도치가 더 이상 움직일 곳이 없다면 KAKTUS
                break;
            for (i = 0; i < k; i++) {
                p = q_h.remove();
                if (p.x == p_d.x && p.y == p_d.y) { // 비버 굴에 도착했다면
                    bw.write(String.valueOf(cnt) + "\n"); // 얼마나 걸렸는지 출력
                    bw.flush();
                    System.exit(0);
                }
                bfs_h(p);
            }
            cnt++;
        }
 
        bw.write("KAKTUS\n");
        bw.flush();
 
    }
}