BOJ 2589 보물섬

초기 아이디어

부분적으로 최단거리를 구하는 문제이므로 DFS, BFS 가 쓰일 것 같다는 생각은 바로 들었는데, 다소 복잡하다. 처음엔 "가장 먼 두 지점" 이라는 말에서 DFS 를 생각했는데 돌아서 가면 안된다는 조건 때문에 결국 가장 먼 지점이라고 해도 BFS 로 풀어내야 한다는 것을 깨달았다. 모든 육지에 대해서 BFS 를 수행하고 가장 멀리까지 갈 수 있는 지점을 계산 해보기로 했다.

문제풀이

1.  모든 두 지점을 순회하면서 BFS

#include<bits/stdc++.h>
using namespace std;

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

int bfs(int sX, int sY){
    queue<pair<int, int>> q;
    q.emplace(sX, sY);
    visited[sX][sY] = 1;
    int ret = 0;
    while(!q.empty()){
        pair<int, int> now = q.front(); q.pop();
        for(int i=0;i<4;i++){
            int nx = now.first + dx[i];
            int ny = now.second + dy[i];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(a[nx][ny]=='W' || visited[nx][ny]) continue;
            q.emplace(nx, ny);
            visited[nx][ny] = visited[now.first][now.second] + 1;
            ret = max(ret, visited[nx][ny]);
        }
    }
    return ret-1;
}

int main(){
    cin >> n >> m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j] == 'W') continue;
            memset(visited, 0, sizeof(visited));
            int b = bfs(i, j);
            ans = b > ans ? b : ans;
        }
    }
    cout << ans;
}

---

다소 복잡한 문제였는데, 사실 이런 문제는 대부분 시간초과가 날까? 하는 의구심 때문에 더 오래걸리는 경향이 있는 것 같다.