[백준 3055번][Java] 탈출 - BFS

www.acmicpc.net/problem/3055

3055번: 탈출

 

BFS 방식을 사용해 최단 거리를 찾는 문제입니다.

 

포인트는 두 가지입니다.

1. 노드를 큐에 넣을 때, 물에 잠기는 장소인지 검사할 것

2. BFS의 깊이가 깊어질 때마다 잠기는 부분이 확산되도록 구현

 

1번은 해당 지역 상하좌우로 물이 있는지 검사하면 됩니다.

2번은 큐에서 꺼내져 나오는 노드의 depth가 깊어질때마 수행해줍니다.

 

둘 다 그리 어려운 구현은 아니라 딱히 할말은 없지만, 코드를 정리하지 않으면서 구현하면

조건들을 처리하면서 실수할 여지가 좀 있는 문제 같네용.

 

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

/*
탈출
 */
public class Main {
    static int R,C;
    static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken()); C = Integer.parseInt(st.nextToken());
        map = new char[R][C];

        for (int i = 0; i < R; i++) {
            String row = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = row.charAt(j);
            }
        }
        int shortestTime = goSonic();
        if(shortestTime == -1){
            System.out.println("KAKTUS"); return;
        }
        System.out.println(shortestTime);


    }

    static int[] dr = {1,-1,0,0};
    static int[] dc = {0,0,1,-1};

    private static int goSonic() {
        boolean[][] discovered = new boolean[R][C];
        Node start = findStartPosition();
        discovered[start.r][start.c] = true;

        Queue<Node> q = new ArrayDeque<>();
        q.add(start);

        int currentDepth = 0;
        while(!q.isEmpty()) {
            Node current = q.poll();

            if(map[current.r][current.c] == 'D') return current.distance;

            if(currentDepth < current.distance) {
                currentDepth = current.distance;

                submerge();
            }

            for (int i = 0; i < 4; i++) {
                int nextR = current.r + dr[i]; int nextC = current.c + dc[i];

                if(isRange(nextR, nextC) && !discovered[nextR][nextC]
                        && !willSubmerge(nextR, nextC)
                        && canGo(nextR, nextC)) {

                    discovered[nextR][nextC] = true;
                    q.add(new Node(nextR, nextC, current.distance+1));
                }
            }
        }

        return -1;
    }


    private static Node findStartPosition() {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == 'S') return new Node(i,j,0);
            }
        }
        throw new RuntimeException("시작 지점 어디감?");
    }

    private static boolean willSubmerge(int r, int c) {
        for (int i = 0; i < 4; i++) {
           int nextR = r + dr[i]; int nextC = c + dc[i];
           if(isRange(nextR, nextC) && map[r][c] == '.' && map[nextR][nextC] == '*') return true;
        }
        return false;
    }

    private static boolean canGo(int r, int c) {
        if(isRange(r, c) && (map[r][c] == '*' || map[r][c] == 'X')) return false;
        return true;
    }

    private static void submerge() {
        boolean[][] visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(!visited[i][j] && map[i][j] == '*') {
                    visited[i][j] = true;
                    submergeAround(i,j, visited);
                }
            }
        }
    }

    private static void submergeAround(int r, int c, boolean[][] visited) {
        for (int i = 0; i < 4; i++) {
            int nextR = r + dr[i]; int nextC = c + dc[i];

            if(isRange(nextR, nextC) && map[nextR][nextC] == '.') {
                visited[nextR][nextC] = true;
                map[nextR][nextC] = '*';
            }
        }
    }

    private static boolean isRange(int r, int c) {
        if(r < 0 || r >= R || c < 0 || c >= C) return false;
        return true;
    }
}
class Node {
    int r, c, distance;

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

    @Override
    public String toString() {
        return "Node{" +
                "r=" + r +
                ", c=" + c +
                ", distance=" + distance +
                '}';
    }
}