🔍 문제 개요
보물섬 지도에서 보물이 묻힌 두 육지(L) 사이의 가장 긴 최단 거리를 구하는 문제입니다.
- 지도는 'L'(육지)와 'W'(바다)로 구성됨
- 상하좌우로만 이동 가능
- 두 육지 간 최단 거리 중 가장 긴 값을 구해야 함
💡 처음 접근: 트리의 지름 알고리즘 (BFS 2회)
아이디어 ✨
- 임의의 'L' 지점에서 BFS → 가장 먼 점 A 찾기
- A에서 다시 BFS → 가장 먼 점 B까지 거리 구하기
이 방식은 트리의 지름을 구할 때 사용하는 전형적인 방법입니다.
구현 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static StringBuilder answerString = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static char[][] map;
private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
/*
* 트리의 지름을 구하는 방식을 이용
* 먼저 맵 전체를 탐색
* L이 발견되는 지점 a 확인
* a에서 bfs 사용해서 가장 멀리있는 지점 b 확인
* b는 해당 L로 이루어진 구역에서 가장 멀리 있는(지름을 만드는 지점) 중 하나
* b에서 bfs 사용해서 가장 멀리있는 지점 c 확인
* b에서 c까지가 해당 L로 이루어진 구역에서의 정답
* 해당 구역의 방문 처리 진행하고 다시 처음 반복문으로 가서 발견되지 않은 L 확인하고 로직 반복
* */
public static void main(String[] args) throws IOException {
inputSetting();
solution();
System.out.println(answerString);
}
private static void solution() {
boolean[][] visited = new boolean[N][M];
int answer = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 'L' && !visited[i][j]) {
int[] result1 = getFarNode(i, j, false, visited);
int[] result2 = getFarNode(result1[0], result1[1], true, visited);
answer = Math.max(answer, result2[2]);
}
}
}
answerString.append(answer);
}
private static int[] getFarNode(int sx, int sy, boolean isReal, boolean[][] visited) {
boolean[][] tmpVisited = isReal ? visited : new boolean[N][M];
int[] result = {sx, sy, 0};
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{sx, sy, 0});
tmpVisited[sx][sy] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int cx = cur[0];
int cy = cur[1];
int cnt = cur[2];
System.out.println(Arrays.toString(cur));
if (result[2] < cnt) {
result[2] = cnt;
result[0] = cx;
result[1] = cy;
}
for (int i = 0; i < 4; i++) {
int nx = cx + dir[i][0];
int ny = cy + dir[i][1];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (tmpVisited[nx][ny]) continue;
if (map[nx][ny] == 'W') continue;
tmpVisited[nx][ny] = true;
queue.add(new int[]{nx, ny, cnt + 1});
}
}
return result;
}
private static void inputSetting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
for (int i = 0; i < N; i++) {
String tmp = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = tmp.charAt(j);
}
}
}
}- 첫 번째 BFS는 가장 먼 노드를 구하기 위함
- 두 번째 BFS에서 실제 거리 계산 및 방문 처리
😢 결과: 반례에서 오답 발생
📌 원인
이 문제는 트리가 아니라 사이클이 존재하는 일반 그래프이기 때문에,
임의의 지점에서 BFS 2번으로는 항상 최장 거리를 보장할 수 없습니다.
📌 반례
4 8
WWWLLLLL
LLWLLLWL
LWLLLLLL
LWLLWWWW내가 작성한 코드를 적용시키면 (0,3) 지점의 L 을 발견하고 BFS로 가장 먼 거리를 찾는다. 그러면, (2,7) 지점의 L이 가장 먼 지점으로 결정됨. 하지만 여기서 가장 긴 최단 거리를 갖는 두 정점은 (0,7) - (3,2) 임(길이 8)
즉, 그래프 내부에 사이클이 존재한다면 트리의 지름을 구하는 방식으로 접근할 수 없음, 트리의 경우에는 특정 지점에서 다른 지점까지 도달하는 경로가 1개이다. 하지만, 그래프의 경우에는 특정 지점에서 다른 지점에 도달하는 경우의 수가 다양하게 존재하기 때문이라고 생각
🔁 두 번째 접근: 모든 'L'에서 BFS 실행
아이디어 🔍
보물섬의 최장 거리는 **"모든 육지에서 시작한 최단 거리의 최대값"**으로 해석 가능하기 때문에,
→ 모든 'L'을 시작점으로 BFS를 돌리는 완전탐색 방식을 사용함
구현 코드
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 'L') {
answer = Math.max(answer, getFarNode(i, j));
}
}
}- 각 'L'마다 BFS를 돌려서 최장 거리 갱신
✅ 결과: 모든 반례 통과
- 사이클 구조도 정확히 계산됨
- 정답 16 정상 출력
⚠️ 왜 트리의 지름 알고리즘은 실패할까?
트리의 지름 알고리즘이 동작하는 이유
- 트리는 사이클이 없고, 노드 간 경로가 유일하기 때문
- BFS 2번만으로 지름의 양 끝을 찾을 수 있음
그러나 보물섬은…
- 사이클이 존재하는 일반 그래프
- 지름의 양 끝을 임의의 시작점에서 찾지 못할 수도 있음
- 결과적으로 부분 구간의 거리만 측정하게 되어 오답
📝 결론 요약
| 방법 | 정확성 | 성능 | 특징 |
|---|---|---|---|
| BFS 2회 (트리 방식) | ❌ 틀릴 수 있음 | 빠름 | 사이클 존재 시 실패 가능 |
| 모든 'L'에서 BFS | ✅ 항상 정답 | 느릴 수 있음 | 완전 탐색 방식 |
💬 개인 회고 & 정리
- 처음에는 알고 있던 "트리의 지름 BFS 2회"를 그대로 적용해도 될 거라 생각했음
- 하지만 그래프의 구조 차이로 인해 예상과 달리 오답 발생
- 결국 모든 L에서 BFS 돌리는 방식이 최적이라는 것을 실험과 반례를 통해 검증
- 이 과정을 통해 이론을 무작정 적용하기보단, 조건을 정확히 따지는 습관의 중요성을 다시 느낌
✅ 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer st;
private static StringBuilder answerString = new StringBuilder();
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static char[][] map;
private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static void main(String[] args) throws IOException {
inputSetting();
solution();
System.out.println(answerString);
}
private static void solution() {
int answer = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 'L') {
answer = Math.max(answer, getFarNode(i, j));
}
}
}
answerString.append(answer);
}
private static int getFarNode(int sx, int sy) {
boolean[][] visited = new boolean[N][M];
int result = 0;
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{sx, sy, 0});
visited[sx][sy] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int cx = cur[0];
int cy = cur[1];
int cnt = cur[2];
result = Math.max(result, cnt);
for (int i = 0; i < 4; i++) {
int nx = cx + dir[i][0];
int ny = cy + dir[i][1];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (visited[nx][ny]) continue;
if (map[nx][ny] == 'W') continue;
visited[nx][ny] = true;
queue.add(new int[]{nx, ny, cnt + 1});
}
}
return result;
}
private static void inputSetting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
for (int i = 0; i < N; i++) {
String tmp = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = tmp.charAt(j);
}
}
}
}
멋있는 사람 - 일단 하자