[백준 2589번] 보물섬

문제 링크:https://www.acmicpc.net/problem/2589 

2589번: 보물섬

<문제 풀이> BFS,  완전탐색

 

각각의 육지에 대해서 BFS로 다른 육지까지 최단거리를 모두 구하고, 최단거리 중에서 최장거리를 찾으면 됩니다.

 

가로, 세로의 크기는 최대 50 이하입니다.

임의의 한 정점에서 다른 모든 정점까지 BFS로 최단 거리를 구하면 O(N*M)의 시간복잡도를 가지고,

최대 정점의 개수는 N*M이므로

전체 시간 복잡도는 O((N*M)^2)의 시간복잡도가 됩니다.

따라서 주어진 시간제한 안에 문제를 해결할 수 있습니다.

 

<C++소스코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
#define X first
#define Y second
 
int n, m;
char board[50][50];
int visited[50][50];
int const dx[4] = { 0, 0, 1, -1 };
int const dy[4] = { 1,-1, 0, 0 };
 
int bfs(int x, int y) {
    fill(&visited[0][0], &visited[49][50], -1);
    queue<pair<int, int> > Q;
    Q.push({ x, y });
    visited[x][y] = 0;
 
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (board[nx][ny] == 'W' || visited[nx][ny] != -1) continue;
            Q.push({ nx, ny });
            visited[nx][ny] = visited[cur.X][cur.Y] + 1;
        }
    }
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ret = max(ret, visited[i][j]); 
        }
    }
    return ret;
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'W')continue;
            ans = max(ans, bfs(i, j)); 
        }
 
    }
    cout << ans;
    
 
 
    return 0;
 
}