백준 2589 - 보물섬

문제

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

리뷰

BFS를 이용하여 간단히 풀 수 있는 문제였다.

문제에서는 육지중 한 지점에서 다른 지점까지 가장 긴 최단 경로를 구하는
요구하고 있다. 모든 육지 지점에서 BFS를 통해 다른 육지 지점을 탐색하며
가장 긴 길이(maxDist)를 갱신해주는 식으로 로직을 구성하였다.

로직의 시간 복잡도는 visited를 초기화하고 BFS 로직을 실행하는
부분에서 $O((RC)^2)$으로 수렴하고 이는 $R=C=250$인 최악의 경우에도
제한 조건인 1초를 무난히 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int R, C;
    static int[][] map;
    static boolean[][] visited;
    static int maxDist = MIN_VALUE;

    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());

        map = new int[R][C];
        visited = new boolean[R][C];

        String line;
        char val;
        List<Node> starts = new ArrayList<>();

        for (int r = 0; r < R; r++) {
            line = br.readLine();
            for (int c = 0; c < C; c++) {
                val = line.charAt(c);
                map[r][c] = val == 'W' ? 0 : 1;
                if (map[r][c] == 1)
                    starts.add(new Node(r, c, 0));
            }
        }

        for (Node start : starts) {
            initVisited();
            bfs(start);
        }

        System.out.println(maxDist);
        br.close();
    }

    static void initVisited() {
        for (int i = 0; i < visited.length; i++)
            Arrays.fill(visited[i], false);
    }

    static void bfs(Node start) {
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.offer(start);
        visited[start.r][start.c] = true;

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

        int nr, nc;

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            maxDist = Math.max(maxDist, cur.level);

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

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

                if (map[nr][nc] == 0 || visited[nr][nc]) continue;

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

    static class Node {
        int r, c, level;

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

결과