[C++] 백준 2589번: 보물섬 (BFS)

https://www.acmicpc.net/problem/2589

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

보물이 두 지점 간 최단거리 중 가장 긴 시간이 걸리는 지점에 위치할 때, 보물이 있는 위치로 이동하는 최단 시간을 구하여라.

---

시간복잡도 어림하기

BFS 알고리즘

 가중치가 같은 최단거리를 구해야하는 문제이므로 BFS와 DFS를 사용할 수 있습니다. 문제에서는 보물이 묻힌 위치가 두 지점 간 최단거리 중 가장 긴 시간이 걸리는 지점에 위치한다고 했으므로, 모든 지점에 대해 이동할 수 있는 모든 위치에 대한 최단거리를 구해야합니다. 따라서 시간복잡도는 모든 위치 탐색 X BFS 또는 DFS의 시간복잡도 = O(n^4)가 될 것입니다. 문제에서 n의 최댓값은 50이고 50^4는 6백만 정도이므로 제한 시간내에 문제를 해결하기 충분합니다.

---

알고리즘 설계하기

 코드 흐름을 먼저 설계해봅시다.

1. 각 지점을 시작 위치로 하여 모든 지점간 최단거리를 구한다.
2. 구한 최단 거리의 최댓값이 보물이 묻힌 위치이다.

 위와 같이 3단계로 구성할 수 있습니다.

 

 1번 단계는 모든 지점에 대해 dfs를 실행하여 해결할 수 있습니다. 이때, 모든 지점에 대해 독립적으로 실행해야하므로 dfs를 실행하기 전 방문처리 배열을 초기화해야 합니다.

 

 2번 단계는 dfs를 실행하면서 최단 거리 값의 최댓값을 구하면 됩니다.

 

 dfs를 실행할 때 주의해야할 점은 이동은 땅으로만 할 수 있다는 점입니다. dfs는 다음과 같은 순서로 구성되는데

1. 시작 위치 방문 처리 및 queue에 push
2. queue가 빌 때까지 아래 동작 수행
2-1. queue에서 가장 앞 위치 꺼내기
2-2. 꺼낸 위치에 대해 이동할 수 있는 다음 위치 구하기.
2-3. 다음 위치를 방문하지 않았거나 이동 가능하다면 queue에 push 및 방문처리
2-4. 2-1 수행하기

 2-3 단계에서 다음 위치의 유효성을 판단할 때 반드시 다음 위치가 땅인지 바다인지 확인해야 합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
#include<tuple>
#include<cstring>
using namespace std;

int n, m, ret, visited[54][54]; 
int dy[] = {-1, 0, 1, 0}; 
int dx[] = {0, 1, 0, -1}; 
char a[54][54];

void bfs(int y, int x){
	/*이전 시행 정보 제거*/
    memset(visited, 0, sizeof(visited));
    
    queue<pair<int, int>> q; 
    q.push({y, x}); visited[y][x] = 1;
    while(q.size()){
        tie(y, x) = q.front(); q.pop(); 
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i]; 
            int nx = x + dx[i]; 
            if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue; 
            if(a[ny][nx] == 'W')continue; //땅이 아닌 경우
            visited[ny][nx] = visited[y][x] + 1; //최단거리 갱신
            q.push({ny, nx});
            ret = max(ret, visited[ny][nx]); //가장 긴 최단거리 갱신
        }
    }
    return;
}
int main(){
    cin >> n >> m; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j]; 
        }
    }
    /*모든 지점에 대해 dfs 실행*/
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 'L') bfs(i, j); 
        }
    } 
    cout << ret - 1 << '\n';
}

 로직 실행 순서는 이전 단계에서 살펴본 것과 같습니다. 이 문제에서 가장 중요한 부분은 각 위치에서 dfs를 실행할 때마다 이전 방문 정보를 초기화하는 부분입니다. 각 경우에 따라 독립적으로 시행되어야 하므로 반드시 dfs를 실행하기 전에 모든 정보를 초기화 해야합니다.

---