Q. 3055 자바 : 탈출

Q. 3055 자바 : 탈출

 

문제 : boj.kr/3055

골드 4 난이도의 문제이다.

 

격자형 그래프가 주어지고,

비어있는 곳은 '.', 물이 차있는 지역은 '*', 돌은 'X',  비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 주어질 때

S가 D로 갈 수 있는 최단경로를 계산하는 문제이다.

 

주의해야 할 점은 물이 차있는 지역인 *는 비어있는 곳 '.'로 확산되고,

물이 차있는 지역은 고슴도치가 갈 수 없다는 점 이다.

 

어떻게 풀지 고민을 해봤더니, 먼저 물이 차있는 곳에 대해 BFS를 하고

이후에 고슴도치가 BFS를 하면 풀 수 있을 것 같아 이렇게 풀었다.

1. 물이 차있는 곳을 큐에 넣는다.

2. 고슴도치의 위치는 저장했다가, 물이 차있는 곳이 모두 큐에 들어가면 이후에 큐에 넣는다.

3. 탐색을 할 때 물인지 고슴도치인지에 따라 조건을 맞춰서 탐색을 한다.

4. 만약 고슴도치(S)가 도달한 곳이 비버의 굴(D)인 경우 이동 횟수를 반환하고 종료한다.

 

그래프의 크기 R, C가 각각 50 이하이므로 시간복잡도는 아래와 같다.

1. 물에 대한 그래프 탐색 - 약 O(RC)

2. 고슴도치에 대한 그래프 탐색 - O(RC)

따라서 약 O(R * C) 정도의 시간복잡도를 가진다고 예상할 수 있다.

 

이 문제의 경우 R과 C의 최대값이 50이므로, 50^2 = 2500으로

시간초과는 걱정하지 않아도 된다.

자료형은 들어오는 타입이 너무 많으므로 char형식의 2차원 배열로 해결했다.

---

풀이는 아래와 같다.

import java.io.*;
import java.util.*;


public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int R, C;
    static char[][] graph;
    static boolean[][] visit;

    static int[] dy = new int[] {0, 1, 0, -1};
    static int[] dx = new int[] {1, 0, -1, 0};
    static Queue<int[]> que;
    static int[] locS;

    static void input() {

        R = scan.nextInt();
        C = scan.nextInt();

        visit = new boolean[R][C];
        graph = new char[R][C];

        for (int i = 0; i < R; i++) {
            graph[i] = scan.next().toCharArray();
        }
    }

    static int bfs() {

        while (!que.isEmpty()) {
            int[] curLoc = que.poll();
            for (int i = 0; i < 4; i++) {
                int ny = curLoc[0] + dy[i];
                int nx = curLoc[1] + dx[i];
                if (ny < 0 || nx < 0 || ny >= R || nx >= C) continue;
                if (curLoc[2] == -1) { // water
                    if (graph[ny][nx] == '.' || graph[ny][nx] == 'S') {
                        graph[ny][nx] = '*';
                        que.add(new int[] {ny, nx, -1});
                    }
                }else {
                    if (visit[ny][nx]) continue;
                    if (graph[ny][nx] == '*') continue;
                    if (graph[ny][nx] == 'X') continue;
                    if (graph[ny][nx] == 'D') {
                        return curLoc[2] + 1;
                    }
                    visit[ny][nx] = true;
                    que.add(new int[] {ny, nx, curLoc[2] + 1});
                }
            }
        }
        return 101;
    }

    static void pro() {

        que = new LinkedList<>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (graph[i][j] == 'X') continue;
                if (graph[i][j] == '.') continue;
                if (graph[i][j] == '*') {
                    que.add(new int[] {i, j, -1}); // y, x, move
                    continue;
                }
                if (graph[i][j] == 'S') {
                    visit[i][j] = true;
                    locS = new int[] {i, j, 0}; // y, x, move
                }
            }
        }
        que.add(locS);

        int res = bfs();
        if (res == 101) sb.append("KAKTUS");
        else sb.append(res);

        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        pro();
    }


    static class FastReader {
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}