[백준/C++] 2589번: 보물섬

문제&링크

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

 

풀이

1. 가장 먼 두 점 사이의 거리를 구하는 문제임으로 시간 초과를 고려하여 BFS로 문제를 해결한다.

2. 육지("L")로 이루어진 그래프가 여러 개 있을 수 있으므로, 모든 점을 기준으로 BFS를 구하고 거리의 최댓값을 구한다.
-> 시간복잡도를 줄이기 위해서 각 그래프 별로 한 점을 잡고 두 번의 BFS를 사용하여 그래프 내의 거리의 최댓값을 구할 수 있다. (트리의 지름 활용) 

3. 각 점별로 BFS를 실행할 때마다 cstring 헤더 파일의 memset 함수를 이용해서 거리(dist) 및 방문 여부(check) 배열을 초기화한다.

4. BFS 함수를 통해 얻은 거리의 최댓값을 반환하도록 하여 다른 BFS 함수를 통해 얻은 거리의 최댓값과 비교한다.

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int N, M;

char map[51][51];
int dist[51][51] = {0};
bool check[51][51] = {false};

int bfs(int s_x, int s_y) {
    memset(dist, 0, sizeof(dist));
    memset(check, false, sizeof(check));

    queue<pair<int, int>> q;
    q.push(make_pair(s_x, s_y));
    
    check[s_x][s_y] = true;
    int max_dist = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int m_x = dx[i] + x;
            int m_y = dy[i] + y;
            
            if (m_x < 1 || m_y < 1 || m_x > N || m_y > M) continue;
            if (map[m_x][m_y] == 'L' && !check[m_x][m_y]) {
                dist[m_x][m_y] = dist[x][y] + 1;
                check[m_x][m_y] = true;
                max_dist = max(max_dist, dist[m_x][m_y]);
                q.push(make_pair(m_x, m_y));
            }
        }
    }

    return max_dist;
}

int main() {
    cin >> N >> M;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
    
    int ans = 0;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j] == 'L') {
                ans = max(ans, bfs(i, j));
            }
        }
    }
    
    cout << ans;
}