백준 3055 - 탈출

문제

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

리뷰

BFS를 통해 풀이할 수 있는 문제였다.

주어진 맵의 정보를 받아 S에서 D까지 도달 가능한 지 BFS를 통해 도출하는 것이
문제의 조건이다. 유의할 점은 물의 위치가 하나가 아닐 수 있다는 것이다.

로직의 구성은 간단하다. 우선, 각 위치를 표현하기 위해 Node라는 클래스를
이용하였다. 좌표를 나타내는 필드외 d 필드는 BFS를 진행하며 해당 경로에서 누적된
거리를 표시하는 용도로 물의 경우 -1값을 넣어주어 고슴도치와 구분하였다.

방문 표시 배열(visited)와 BFS에 사용할 큐를 미리 설정해둔뒤 입력값을 받으며
시작점과 끝점일 경우 위치를 저장하고, 물일 경우엔 큐에 미리 넣어주었다.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.

위 조건으로 인해 BFS 진행시 물이 먼저 상하좌우로 전파되고 고슴도치가 이동하는
형태로 로직이 전개되어야 하기 때문이다. 이외 돌로 막혀있는 곳은 해당 위치를 미리
visited[r][c]=true 설정하여 처리했다.

위와 같이 입력을 받으며 설정을 마친뒤 BFS를 실행하며 물을 전파하고, 고슴도치를
이동시켜 도달이 가능한 경우 최단 거리를, 불가능한 경우 -1을 반환하여 답을
도출하였다.

로직의 시간복잡도는 BFS의 정점의 개수 $N=R \times C$일 때 $O(N^2)$ 꼴이고
$N^2=(50 \times 50)^2=250^2$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int R, C;
    static boolean[][] visited;
    static Queue<Node> queue = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = parseInt(st.nextToken());
        C = parseInt(st.nextToken());

        visited = new boolean[R][C];

        Node start, water, end;
        start = end = null;

        for (int r = 0; r < R; r++) {
            String line = br.readLine();

            for (int c = 0; c < C; c++) {
                char value = line.charAt(c);

                if (value == 'S') {
                    start = new Node(r, c, 0);
                } else if (value == '*') {
                    water = new Node(r, c, -1);
                    queue.offer(water);
                } else if (value == 'D') {
                    end = new Node(r, c, 0);
                } else if (value == 'X')
                    visited[r][c] = true;
            }
        }


        int result = bfs(start, end);
        System.out.println(result == -1 ? "KAKTUS" : result);
        br.close();
    }


    static int bfs(Node start, Node end) {
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        visited[start.r][start.c] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            if (cur.d > 0 && cur.r == end.r && cur.c == end.c) return cur.d;

            for (int i = 0; i < dr.length; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];

                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;

                if (visited[nr][nc]) continue;

                if (cur.d == -1 && nr == end.r && nc == end.c) continue;

                visited[nr][nc] = true;
                queue.offer(new Node(nr, nc, cur.d == -1 ? -1 : cur.d + 1));
            }
        }

        return -1;
    }


    static class Node {
        int r, c, d;

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

결과