🏆 알고리즘 문제 풀이
📌 문제 정보
- 문제명 : 보물섬
- 문제 번호 : 2589
- 출처 : https://www.acmicpc.net/problem/2589
- 난이도 : G5
- 유형 : 그래프 / BFS
🧐 문제 설명
보물섬 지도에서 보물이 묻혀 있는 두 지점을 찾아,
서로 간의 최단 거리로 이동하는 데 걸리는 시간(칸 수) 중 가장 긴 시간을 구하는 문제이다.
- 지도는
L(육지)과W(바다)로 구성된다. L끼리만 인접 이동 가능하며, 같은 곳을 두 번 이상 지나갈 수 없다.- 상하좌우로 인접한 칸만 이동할 수 있다.
- 최단 경로 중 가장 긴 거리(= 최장 최단거리) 를 구하면 된다.
👉 출력 : 가장 멀리 떨어진 두 육지(L) 사이의 최단 거리(이동 칸 수)
💡 접근 방법
-
모든 육지(L)에서 BFS 탐색 수행
- 각 육지를 시작점으로 BFS 수행하여,
- 해당 위치에서 갈 수 있는 다른 육지까지의 최단 거리 계산
- 그 중 가장 큰 거리를 결과로 갱신
- 각 육지를 시작점으로 BFS 수행하여,
-
BFS로 최단거리 탐색
- BFS는 최단거리 탐색에 최적화된 알고리즘
dist배열을 사용하여 현재 위치까지 이동한 칸 수를 저장
-
중복 방문 방지
- 각 BFS 시작 시
visited배열을 새로 초기화하여- 이전 BFS의 방문 기록과 혼동되지 않게 함
- 각 BFS 시작 시
📝 문제 설계
✅ 변수 정의
| 변수 | 설명 |
|---|---|
x, y | 지도 크기 (행, 열) |
arr[][] | 지도 정보 (L, W) |
visited[][] | 방문 체크용 |
dx, dy | 상하좌우 이동 방향 |
ans | 최종 결과값 (가장 긴 최단거리) |
✅ 알고리즘 흐름
- 입력으로 지도의 행(
x), 열(y), 지도 데이터(arr[][]) 받기 - 지도 전체를 순회하며
L(육지)일 경우 BFS 탐색 수행 - BFS를 통해 해당 육지에서 가장 먼 육지까지의 거리 계산
- 최대값을
ans에 저장 - 모든 BFS 탐색 종료 후
ans출력
✅ 시간 복잡도
- 지도 크기: 최대
50 x 50 = 2500 - 각 육지마다 BFS 실행 시 최악의 경우
O(N*M*N*M)→ 약6,250,000연산
→ 충분히 통과 가능 (BFS는 매우 빠름)
💡 사용 알고리즘
- BFS (너비 우선 탐색, Breadth-First Search)
📚 BFS를 선택한 근거
-
모든 간선의 가중치가 동일한 그래프(또는 격자)에서 한 지점에서 다른 지점까지의 '최단 거리'를 구하기에 적합하다.
-
DFS(깊이 우선 탐색)는 경로의 깊이에 따라 불필요하게 멀리 탐색할 수 있지만 BFS는 가까운 칸부터 순차적으로 탐색하므로 '최소 이동 거리'를 보장할 수 있다.
-
문제에서 요구하는 것은 "한 육지에서 다른 육지까지의 최단 거리 중 최댓값"이므로,
각 육지를 시작점으로 BFS를 수행해 해당 지점에서 도달 가능한 최장 거리(farthest)를 구하는 것이 최적의 접근법이다.
입력 & 출력 예시
🧑💻 코드
package Baekjoon;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class B_2589_보물섬 {
static int x, y;
static char[][] arr;
static boolean[][] visited;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
public static void main(String[] args) {
// 육지(L) / 바다(W)
// 보물은 서로 간에 최단 거리로 이동하는 데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.
// 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.
Scanner sc = new Scanner(System.in);
x = sc.nextInt();
y = sc.nextInt();
arr = new char[x][y];
visited = new boolean[x][y];
for (int i = 0; i < x; i++) {
String line = sc.next();
for (int j = 0; j < y; j++) {
arr[i][j] = line.charAt(j);
}
}
int ans = 0;
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (arr[i][j] == 'L') ans = Math.max(ans, bfs(i, j));
}
}
System.out.println(ans);
}
// BFS로 시작점(sr, sc)에서 가장 먼 육지까지의 거리 계산
static int bfs(int sr, int sc) {
Deque<int[]> q = new ArrayDeque<>();
boolean[][] visited = new boolean[x][y];
int[][] dist = new int[x][y];
visited[sr][sc] = true;
q.add(new int[]{sr, sc});
int farthest = 0; // 시작점에서 가장 먼 거리
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
for (int d = 0; d < 4; d++) {
int nr = r + dx[d];
int nc = c + dy[d];
// 1) 경계 검사
if (nr < 0 || nr >= x || nc < 0 || nc >= y) continue;
// 2) 이동 가능한 칸인지 검사
if (arr[nr][nc] != 'L') continue;
// 3) 방문 여부 확인
if (visited[nr][nc]) continue;
visited[nr][nc] = true;
dist[nr][nc] = dist[r][c] + 1;
farthest = Math.max(farthest, dist[nr][nc]);
q.add(new int[]{nr, nc});
}
}
return farthest; // 가장 먼 육지까지의 최단거리 반환
}
}🔍 코드 해설
1️⃣ BFS로 최단거리 계산
static int bfs(int sr, int sc) {
Deque<int[]> q = new ArrayDeque<>();
boolean[][] visited = new boolean[x][y];
int[][] dist = new int[x][y];
}- BFS를 수행할 큐(Deque)와 방문 배열(visited), 거리 배열(dist) 선언
- visited와 dist는 매 BFS마다 새로 초기화 (시작점마다 별도의 탐색)
2️⃣ 큐 초기 세팅
visited[sr][sc] = true;
q.add(new int[]{sr, sc});- 시작점을 방문 처리 후 큐에 추가
3️⃣ BFS 탐색 과정
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
}- 큐에서 현재 좌표를 꺼내어 인접 4방향 탐색 시작
4️⃣ 유효한 이동 조건
if (nr < 0 || nr >= x || nc < 0 || nc >= y) continue; // 지도 범위
if (arr[nr][nc] != 'L') continue; // 육지인지 검사
if (visited[nr][nc]) continue; // 이미 방문했는지 검사- 지도 밖이거나 바다(W)이거나 이미 방문한 칸이면 skip
5️⃣ 거리 갱신 및 큐 삽입
visited[nr][nc] = true;
dist[nr][nc] = dist[r][c] + 1;
farthest = Math.max(farthest, dist[nr][nc]);
q.add(new int[]{nr, nc});- 현재 칸에서 인접 칸으로 한 칸 이동 → dist + 1
- 가장 먼 거리(farthest) 갱신
6️⃣ 결과 반환
return farthest;- BFS가 종료되면 시작점에서 가장 먼 육지까지의 최단거리 반환
