[백준] 3055번 탈출(java)

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

3055번: 탈출

bfs 문제이다.

 

핵심

S에서 D로 도달하는 것이 기본적인 목표이다. 하지만 물이 있는 곳은 건널 수 없고, 물 또한 퍼지기 때문에 이를 잘 고민해야 한다.

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static char[][] map;
    static int r;
    static int c;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
        map = new char[r][c];

        int sY = 0;
        int sX = 0;

        for (int i = 0; i < r; i++) {
            String line = sc.next();
            for (int j = 0; j < c; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'S') {
                    sY = i;
                    sX = j;
                }
            }
        }

        int result = bfs(sY, sX);
        System.out.println(result == -1 ? "KAKTUS" : result);
    }

    private static int bfs(int sY, int sX) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sY, sX});
        int[][] dis = new int[r][c];
        dis[sY][sX] = 1;

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (map[i][j] == '*') {
                    q.offer(new int[]{i, j});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] move = q.poll();
            char now = map[move[0]][move[1]];

            for (int i = 0; i < 4; i++) {
                int moveY = move[0] + dy[i];
                int moveX = move[1] + dx[i];

                if (validation(moveY, moveX)) {
                    continue;
                }

                if (now == 'S') {
                    if (map[moveY][moveX] == 'D') {
                        return dis[move[0]][move[1]];
                    }
                    if (map[moveY][moveX] == '.') {
                        map[moveY][moveX] = 'S';
                        q.offer(new int[]{moveY, moveX});
                        dis[moveY][moveX] = dis[move[0]][move[1]] + 1;
                    }
                }

                if (now == '*') {
                    if (map[moveY][moveX] == '.' || map[moveY][moveX] == 'S') {
                        map[moveY][moveX] = '*';
                        q.offer(new int[]{moveY, moveX});
                    }
                }
            }
        }
        return -1;
    }

    private static boolean validation(int moveY, int moveX) {
        return !(0 <= moveY && moveY < r && 0 <= moveX && moveX < c);
    }
}

해설

다른 사람들의 풀이도 보았는데, 대부분의 경우에 물과 고슴도치의 움직임을 따로 분리하여 풀었다.

나의 경우에는 한 번에 시도하였다.

우선 접근방법은 이러하다. 고슴도치가 먼저 이동하고, 이후 나머지 물이 퍼지게 된다.

물은 고슴도치의 위치를 덮을 수 있다.

따라서 중요한 점은 bfs를 시작할 때 처음 넣는 값은 반드시 고슴도치가 되어야 한다.

나머지는 코드를 보면 쉽게 이해할 수 있다.

 

 

배운 점

이 문제를 푸는데 조금 오래 걸렸다. 실수로 인해 시간이 걸렸는데 이유가 매우 어이없을 정도로 단순한 문제였다.

처음에는 내 접근방법이 잘못된 줄 알고, 계속해서 반례를 생각했으나 찾지 못하였고 포기하고 다른 사람들의 풀이대로

풀까 고민도 하였다. 하지만 끝내 내가 처음 생각한 풀이로 풀게 되었다.

맞게 접근하였더라도 작은 실수로 인해 실패하게 된다. 

따라서 꼼꼼하게 체크하는 습관을 가져야겠다.