백준 2589 : 보물섬 [JAVA]

[문제 링크]

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

[난이도]

- Gold 5

 

[알고리즘]

- BFS

 

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int L, W;
    static char[][] graph;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        graph = new char[L][W];
        Queue<int[]> LandPos = new LinkedList<>();
        for (int i = 0; i < L; i++) {
            String input = br.readLine();
            for (int j = 0; j < W; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'L') {
                    LandPos.add(new int[]{i, j});
                }
            }
        }

        int Treasure = 0;
        while (!LandPos.isEmpty()) {
            int[] Land = LandPos.poll();
            int LandX = Land[0];
            int LandY = Land[1];
            Treasure = Math.max(Treasure, bfs(LandX, LandY));
        }
        System.out.println(Treasure);
    }

    static int bfs(int LandX, int LandY) {
        int max = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{LandX, LandY, 0});
        boolean[][] visited = new boolean[L][W];
        visited[LandX][LandY] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            max = Math.max(max, count);
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < L && ny >= 0 && ny < W) {
                    if (!visited[nx][ny]) {
                        if (graph[nx][ny] == 'L') {
                            visited[nx][ny] = true;
                            queue.add(new int[]{nx, ny, count + 1});
                        }
                    }
                }
            }
        }
        return max;
    }
}

[풀이]

입력을 받을 때 모든 육지인 좌표를 큐에 담아둔 후, 큐에서 하나씩 꺼내며 해당 좌표를 시작으로 4방탐색을 반복해서(육지의 개수만큼) 실행해야 한다. 4방탐색을 하며 한칸 이동할 때 마다 count를 1씩 증가시키고 그 count의 최대값 return 해준다. return 해준 값들 중 최대값을 다시 찾아 출력해준다.