[랜덤 마라톤] 보물섬(2589)

1. 문제 풀이 아이디어

• 모든 지역에 대해 BFS를 사용해 각 지역에서의 최대 거리를 구하고, 그 최대값을 찾아 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        boolean[][] map = new boolean[n][m];
        int result = 0;
        for (int i = 0; i < n; i++) {
            String line = bufferedReader.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = line.charAt(j) == 'L';
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!map[i][j])
                    continue;
                boolean[][] chk = new boolean[n][m];
                chk[i][j] = true;
                Queue<int[]> que = new ArrayDeque<>();
                que.add(new int[]{i, j});
                int dist = -1;
                while (!que.isEmpty()) {
                    int size = que.size();
                    dist++;
                    for (int k = 0; k < size; k++) {
                        int[] cur = que.poll();
                        for (int l = 0; l < dir.length; l++) {
                            int x = cur[0] + dir[l][0];
                            int y = cur[1] + dir[l][1];
                            if (x < 0 || x >= n || y < 0 || y >= m || chk[x][y] || !map[x][y]) continue;
                            chk[x][y] = true;
                            que.add(new int[]{x, y});
                        }
                    }
                }
                result = Math.max(result, dist);
            }
        }
        System.out.println(result);
        bufferedReader.close();
    }
}

3. 정리

• 입력을 받아 map 배열에 육지(L)일 경우 true로 저장한다.

• 전체 map 배열을 순회하며 육지인 위치(true)에서 BFS를 시작한다.

• BFS에서는 현재 위치를 que에 넣고, 방문 여부를 체크하기 위해 chk 배열을 사용한다.

• que가 빌 때까지, 현재 que의 크기만큼 반복하면서 주변 이동 가능한 위치를 탐색해 que에 추가한다.

• 각 BFS의 최대 거리를 dist로 계산하여 result와 비교해 더 큰 값을 저장한다.

• 모든 BFS가 끝난 후, result를 출력하여 문제를 해결한다.