이번에는 백준 2589번 보물섬 문제를 풀어보았습니다.
문제를 처음 봤을 때 두 지점 사이의 최단 거리를 구해야 한다는 점에서 BFS가 떠올랐습니다.
보물은 서로 가장 멀리 떨어져 있는 두 육지에 묻혀 있으므로, 모든 육지에서 BFS를 수행하여 도달 가능한 가장 먼 육지까지의 거리를 구한 뒤 그 중 최댓값을 구하는 방식으로 구현하였습니다.
문제 설명
지도에는 육지(L)와 바다(W)가 표시되어 있습니다.
상하좌우로 인접한 육지로만 이동할 수 있으며, 한 칸 이동하는 데 1시간이 걸립니다.
보물은 서로 최단 거리로 이동했을 때 가장 오래 걸리는 두 육지에 묻혀 있습니다.
보물이 묻혀 있는 두 지점 사이의 최단 이동 시간을 구하는 문제입니다.
풀이 아이디어
먼저 모든 육지의 위치를 저장하였습니다.
이후 각각의 육지를 시작점으로 하여 BFS를 수행하였습니다.
BFS를 수행하면서 현재 위치에서 도달 가능한 육지들의 거리를 visited 배열에 저장하였습니다.
방문할 때마다 거리를 갱신하고, 가장 큰 거리를 max_distance에 저장하였습니다.
모든 육지에 대해 BFS를 수행한 뒤 가장 큰 거리를 출력하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> inp_map;
vector<pair<int, int>> lands;
vector<vector<int>> visited;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int L, W;
int main() {
cin >> L >> W;
for (int i=0; i < L; i++) {
inp_map.push_back(vector<int>());
visited.push_back(vector<int>());
string temp;
cin >> temp;
for (int j=0; j < W; j++) {
if (temp[j] == 'W')
inp_map[i].push_back(0);
else {
inp_map[i].push_back(1);
lands.push_back(make_pair(i, j));
}
visited[i].push_back(0);
}
}
int max_distance = -1;
for (pair<int, int> land : lands) {
queue<pair<int, int>> q;
q.push(land);
int distance = 0;
visited[land.first][land.second] = 1;
while(!q.empty()) {
pair<int, int> p = q.front();
q.pop();
for (int i=0; i<4; i++) {
int ny = p.first + dy[i];
int nx = p.second + dx[i];
if (ny >= 0 && nx >= 0 && ny < L && nx < W) {
if (inp_map[ny][nx] == 1 && !visited[ny][nx]) {
q.push(make_pair(ny, nx));
visited[ny][nx] = visited[p.first][p.second] + 1;
max_distance = max(max_distance, visited[ny][nx]);
}
}
}
}
fill(visited.begin(), visited.end(), vector<int>(W,0));
}
cout << max_distance-1 << '\n';
return 0;
}풀이 흐름
- 입력을 받으면서 육지와 바다를 구분하여 저장합니다.
- 육지인 경우 lands 벡터에 좌표를 저장합니다.
- 저장해둔 모든 육지를 시작점으로 BFS를 수행합니다.
- BFS를 진행하면서 방문한 위치의 거리를 visited 배열에 저장합니다.
- 방문할 때마다 가장 긴 거리를 max_distance에 저장합니다.
- 하나의 BFS가 끝나면 visited 배열을 초기화합니다.
- 모든 육지에 대해 BFS를 수행한 뒤 최종 결과를 출력합니다.
구현 포인트
1. 육지 위치 미리 저장
입력을 받는 과정에서 육지인 위치를 따로 저장하였습니다.
if (temp[j] == 'W')
inp_map[i].push_back(0);
else {
inp_map[i].push_back(1);
lands.push_back(make_pair(i, j));
}이후 저장된 육지들을 시작점으로 BFS를 수행하였습니다.
2. 방문 배열에 거리 저장
이 코드에서는 단순 방문 여부뿐만 아니라 거리 정보도 함께 저장하였습니다.
visited[land.first][land.second] = 1;시작 위치를 1로 두고 탐색을 진행하였습니다.
visited[ny][nx] = visited[p.first][p.second] + 1;현재 위치의 거리에서 1을 증가시키는 방식으로 거리를 계산하였습니다.
3. BFS 수행
각 육지를 시작점으로 큐를 이용한 BFS를 수행하였습니다.
queue<pair<int, int>> q;
q.push(land);상하좌우 방향으로 탐색하면서 방문하지 않은 육지만 큐에 추가하였습니다.
if (inp_map[ny][nx] == 1 && !visited[ny][nx])4. 최장 거리 갱신
새로운 육지를 방문할 때마다 최장 거리를 갱신하였습니다.
max_distance = max(max_distance, visited[ny][nx]);모든 BFS 과정에서 가장 큰 값을 저장하도록 하였습니다.
5. BFS 종료 후 visited 초기화
한 시작점에 대한 BFS가 끝나면 다음 BFS를 위해 visited 배열을 초기화하였습니다.
fill(visited.begin(), visited.end(), vector<int>(W,0));모든 육지를 시작점으로 사용해야 하므로 매 탐색마다 초기화가 필요하였습니다.
6. 시작 지점을 1로 두었기 때문에 마지막에 1 감소
거리 계산 시 시작 위치를 1로 설정하였습니다.
visited[land.first][land.second] = 1;따라서 실제 이동 시간은 1이 더해진 상태로 계산되므로 출력할 때 1을 빼주었습니다.
cout << max_distance-1 << '\n';