백준 2589 - 보물섬

문제

접근

  1. 모든 육지에서 시작해보기 -> 모든 L이 잠재적 보물의 시작점일 수 있음
  2. 따라서 각 시작점에서 BFS를 실행 -> 모든 육지까지의 최단 거리.
  3. 그 중 가장 길었던 거리 기록
  4. 전체 거리 중 가장 긴 거리 찾기

이와 같은 괒어을 통해 육지와 육지 사이의 최단 경로지만, 최대인 경로를 찾을 수 있을 것이라는 판단.

구현 전

  1. 지도 저장
    1. 하지만 자바로 2차원 배열을 저장하는 것은 여전히 쉽지 않음…
  2. 큐
  3. 좌표 그리고 거리
  4. 방문 배열
  5. 이동 방향 (dr dc)

구현

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

public class Main {

    // 상하좌우 이동을 위한 방향 배열
    static int[] dr = {-1, 1, 0, 0}; // 위, 아래
    static int[] dc = {0, 0, -1, 1}; // 왼쪽, 오른쪽

    // BFS 탐색 시 큐에 저장할 지점 정보 클래스
    static class Point {
        int r, c, dist; // 행, 열, 현재까지의 거리

        public Point(int r, int c, int dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
    }

    // BFS 메서드: 특정 시작점으로부터 도달 가능한 가장 먼 육지까지의 최단 거리를 반환
    private static int bfs(int startR, int startC, int R, int C, char[][] map) {
        // BFS마다 방문 배열을 새로 초기화
        boolean[][] visited = new boolean[R][C];
        Queue<Point> q = new LinkedList<>();

        // 시작 지점을 큐에 넣고 방문 처리
        q.offer(new Point(startR, startC, 0));
        visited[startR][startC] = true;

        int maxDistFromStart = 0; // 현재 BFS의 시작점으로부터의 최대 거리

        while (!q.isEmpty()) {
            Point current = q.poll();
            // 현재 지점까지의 거리가 이 BFS에서의 최대 거리인지 확인 및 갱신
            maxDistFromStart = Math.max(maxDistFromStart, current.dist);

            // 현재 지점에서 상하좌우 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nr = current.r + dr[i]; // 다음 행
                int nc = current.c + dc[i]; // 다음 열

                // 맵 범위 안에 있고 (1), 아직 방문하지 않았으며 (2), 육지('L')인 경우 (3)
                if (nr >= 0 && nr < R && nc >= 0 && nc < C &&
                    !visited[nr][nc] && map[nr][nc] == 'L') {

                    visited[nr][nc] = true; // 방문 처리
                    q.offer(new Point(nr, nc, current.dist + 1)); // 큐에 추가 (거리는 1 증가)
                }
            }
        }
        return maxDistFromStart; // 이 시작점에서 탐색 가능한 최대 거리 반환
    }

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

        int R = Integer.parseInt(st.nextToken()); // 지도의 세로 크기 (행)
        int C = Integer.parseInt(st.nextToken()); // 지도의 가로 크기 (열)

        char[][] map = new char[R][C]; // 지도 정보를 저장할 2차원 문자 배열

        // 지도 정보를 한 줄씩 읽어서 map 배열에 저장
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
            }
        }
        br.close(); // 입력 완료 후 BufferedReader 닫기

        int overallMaxDistance = 0; // 모든 BFS 탐색을 통해 얻은 최종 최장 거리

        // 맵의 모든 칸을 순회하며 육지('L')인 곳에서 BFS 시작
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (map[r][c] == 'L') { // 현재 칸이 육지일 경우에만 BFS 시작
                    // 현재 육지 지점에서 시작하는 BFS를 수행하고 그 안에서의 최대 거리를 얻음
                    int currentStartMaxDist = bfs(r, c, R, C, map);
                    // 전체 최장 거리를 갱신
                    overallMaxDistance = Math.max(overallMaxDistance, currentStartMaxDist);
                }
            }
        }

        System.out.println(overallMaxDistance); // 최종 결과 출력
    }
}

후기

어…. 어렵다…

자바의 LinkedList와 Queue 인터페이스 구현체 공부해야지? 아무래도…