[SDS 알고리즘 특강 복습] 3055 탈출 (BFS)

https://www.acmicpc.net/problem/3055

 

 

BFS 문제.

물큐를 돌리고, 비버(고슴도치)큐를 돌리면 문제가 해결된다.

 

코드는 놀랍게도 짰다.

SDS 특강을 2주동안 들으니 나도 모르는 사이 BFS, DFS를 자바로 짤 수 있는 수준이 된 것 같다.

교육듣기 잘하였고 끝까지 참여하길 정말 잘한 것 같다!

 

그러나 몇가지 치명적인 엣지케이스를 놓쳤다 ㅠㅠ.

 

1. 비버한테 여러번(여러 시간대에) 도달할 수 있는 경우

2. 물큐돌린 이후 물맵이 전부 0인 경우

 

엣지케이스를 초반에 고려하고 코드를 짜야할지, 코드를 짜고 엣지케이스를 고려해야할 지에 대한 고민이 필요해보인다.

 

<내 정답 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int R, C;
    static Queue<int[]> waterQ;
    static Queue<int[]> biberQ;
    static char[][] map;
    static int[][] waterMap;
    static int[][] biberMap;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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];
        waterQ = new LinkedList<int[]>();
        biberQ = new LinkedList<int[]>();
        waterMap = new int[R][C];
        biberMap = new int[R][C];

        String s;
        int[] start = new int[] {0, 0};
        for(int i=0; i<R; i++) {
            s = br.readLine();
            for(int j=0; j<C; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'S') {
                    start = new int[] {i, j};
                }
            }
        }

        // 물 bfs 돌리면서 waterMap에 방문시간 마스킹
        waterBfs();

        // 비버 bfs돌리면서 waterMap 마스킹한 것 참고하여 방문 -> "D"에 도달하면 종료 or 도달불가시 캨터스~
        biberBfs(start);

    }

    static void biberBfs(int[] start) {
        biberQ.add(start);
        int flag = 0;
        while(!biberQ.isEmpty()) {
            int[] cur = biberQ.poll();

            for(int i=0; i<4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(nx>=R || ny>=C || nx<0 || ny<0) continue;
                if(map[nx][ny] == '.' && biberMap[nx][ny] == 0 && (waterMap[nx][ny] > biberMap[cur[0]][cur[1]] + 1 || waterMap[nx][ny] == 0 ))  {
                    // 비버맵 업데이트, 비버큐에 삽입
                    biberMap[nx][ny] = biberMap[cur[0]][cur[1]] + 1;
                    biberQ.add(new int[] {nx, ny});
                }
                if(map[nx][ny] == 'D') {
                    biberMap[nx][ny] = biberMap[cur[0]][cur[1]] +1;
                    System.out.println(biberMap[nx][ny]);
                    flag = 1;
                    biberQ.clear();
                    break;
                }
            }
        }
        if(flag==0) System.out.println("KAKTUS");
    }

    // (a,b)의 좌표에서 시작하는 waterBfs
    static void waterBfs() {
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if (map[i][j] == '*') {
                    waterQ.add(new int[] {i,j});
                }
            }
        }

        while(!waterQ.isEmpty()) {
            int[] cur = waterQ.poll();
            for (int i=0; i<4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if(nx >= R || ny >= C || nx<0 || ny<0) continue;
                if(map[nx][ny] == '.' && waterMap[nx][ny] == 0) {
                    waterMap[nx][ny] = waterMap[cur[0]][cur[1]] +1;
                    waterQ.add(new int[] {nx, ny});
                }
            }
        }
    }
}