[백준 JAVA] 2589 보물섬 (BFS,너비 우선 탐색)

<🔗문제 링크>

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

2589번: 보물섬

 

<✏️문제풀이>

input 저장 시 map에 'L'인 경우 true를 저장 , 'W'인 경우 false를 저장하였습니다.

이문제의 포인트는 한 땅에서 가장 멀리 있는 두 육지를 찾고 두 육지의 까지의 시간을 출력하는 것이라 생각했습니다.

하지만 한 지점에서부터 탐색을 한경우에는 땅이 여러 개인 경우, 가장 긴 두 육지의 시작 노드가 아닌 경우 등  최대 값을 보장할 수 없습니다.

따라서 모든 땅인 지점에서부터 너비 우선 탐색을 하여서 가장 긴 노드를 탐색하여 최댓값을 출력하였습니다.

최댓값을 저장하기 위해서는 visit을 int형 배열로 선언하여 움직일 때마다 +1 하여 저장하도록 하여서 최댓값을 찾았습니다.

 

<📝코드>

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int row, col;
    private static boolean[][] map;
    private static int[][] visited;
    private static List<Integer> dirx = List.of(-1, 1, 0, 0);
    private static List<Integer> diry = List.of(0, 0, -1, 1);

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        map = new boolean[row][col]; //true-> land, false -> water

        saveInput();
        System.out.println(scanMap());
    }

    private static int scanMap() {
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //땅인 경우만 탐색
                if (map[i][j]) max = Math.max(max, bfs(i, j)); 
            }
        }
        return max;
    }

    private static int bfs(int x, int y) {
        visited = new int[row][col];

        int max = 0;
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));
        visited[x][y] = 1;

        while (!q.isEmpty()) {
            Point now = q.poll();
            max = Math.max(max, visited[now.x][now.y]);

            for (int i = 0; i < 4; i++) {
                int mvx = now.x + dirx.get(i);
                int mvy = now.y + diry.get(i);

                //벗어남
                if (mvx >= map.length || mvx < 0 || mvy < 0 || mvy >= map[0].length) continue;

                //땅이고, 방문 안된 노드이면
                if (map[mvx][mvy] && visited[mvx][mvy] == 0) {
                    visited[mvx][mvy] = visited[now.x][now.y] + 1;
                    q.add(new Point(mvx, mvy));
                }
            }
        }
        return max - 1;
    }

    private static void saveInput() throws IOException {
        for (int i = 0; i < row; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < col; j++) {
                char input = temp[j];
                boolean saveInput = false;
                if (input == 'L') saveInput = true; //땅인 경우만 true 리턴
                map[i][j] = saveInput;
            }
        }
    }

}