[Baekjoon 2589 / Java / 골드5] 보물섬

문제

테스트 케이스

 

L이 육지고 W가 바다이다.

상하좌우 육지로만 이동할 수 있다고 했을 때, 보물지도 내에서 가장 먼 두 육지의 거리를 출력하면 된다.

물론 두 육지의 거리는 최단거리여야 한다.

 

import java.io.*;

import java.util.*;

public class 보물섬_2589 {

    // 입력값 저장할 변수, 4방향 탐색할 dx dy 선언

    static int N, M;

    static char[][] maps;

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

        // N, M 입력받기

        N = Integer.parseInt(st.nextToken());

        M = Integer.parseInt(st.nextToken());

        // 보물지도 입력받기

        maps = new char[N][M];

        for(int i = 0; i < N; i++) {

            maps[i] = br.readLine().toCharArray();

        }

        // 보물지도의 모든 좌표를 기준으로 BFS를 진행하며 최대거리를 찾는다

        int result = 0;

        for(int i = 0; i < N; i++) {

            for(int j = 0; j < M; j++) {

                if(maps[i][j] == 'L') {

                    result = Math.max(result, bfs(i, j));

                }

            }

        }

        System.out.println(result);

    }

    // 탐색할지 말지 검사하는 함수

    public static boolean goingNoGoing(int nx, int ny, int[][] visited) {

        if(0 <= nx && nx < N && 0 <= ny && ny < M && maps[nx][ny] == 'L' && visited[nx][ny] == 0) {

            return true;

        }

        return false;

    }

    // bfs 메인 로직

    public static int bfs(int i, int j) {

        // 큐에 시작 좌표 담기

        Queue<int[]> queue = new LinkedList<>();

        queue.add(new int[]{i, j});

        // 배열 선언 시 자동으로 0으로 초기화 된다

        // 시작 좌표 방문 처리

        int[][] visited = new int[N][M];

        visited[i][j] = 1;

        int count = 0;

        // 큐가 빌 때까지 진행

        while(!queue.isEmpty()) {

            int[] here = queue.poll();

            int x = here[0];

            int y = here[1];

            // 상하좌우 4방향 탐색

            for(int k = 0; k < 4; k++) {

                int nx = x + dx[k];

                int ny = y + dy[k];

                // 탐색할 수 있는 위치라면 방문체크 하고 큐에 넣는다

                if(goingNoGoing(nx, ny, visited)) {

                    visited[nx][ny] = visited[x][y] + 1;

                    count = Math.max(count, visited[nx][ny]);

                    queue.add(new int[]{nx, ny});

                }

            }

        }

        return count - 1;

    }

}

 

큐를 사용해서 BFS를 진행했다. visited 배열에 각 육지까지의 거리를 넣어주고, 가장 긴 거리를 출력한다.

BFS는 보물지도의 모든 좌표에 대해서 진행하며, 기존 최대값보다 큰 결과가 나왔을 경우 result를 갱신함으로써 가장 긴 두 육지 사이의 거리를 찾는다.