[알고리즘 문제] 백준2589 - 보물섬

www.acmicpc.net/problem/2589

2589번: 보물섬

 

보물간에 최단거리를 구하는 문제인데, 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 사실 문제를 읽고 "최단 거기로 이동하는 데 있어 가장 긴 시간이 걸리는 ~"이 이해가 잘 안되서 몇번 읽었습니다.

 

중요한 것은 "최단거로 + 가장 긴 시간"을 만족해야 하는데 bfs를 사용하면 자동으로 최단거리를 만족하고 가장 긴 시간은 bfs로 탐색할 때 max값을 계속 갱신해 주면 됩니다. 시작점이 따로 주어진 것이 아니기 떄문에 맵에서 모든 육지부분에 대해 bfs를 해주어야 합니다.

 

그리고 이동 거리는 visited[50][50]에 체크해 주었는데 새로운 위치를 이동할 수 있으면 기존의 위치에서 +1한 값을 넣어주었습니다.

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

using namespace std;

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

string map[51];
int height, width;
int ans = -1;

void bfs(int y, int x)
{
    int visited[51][51] = {0};
    queue<pair<int, int>> que;

    visited[y][x] = 1;
    que.push({y, x});

    while (!que.empty())
    {
        int curY = que.front().first;
        int curX = que.front().second;
        que.pop();

        ans = max(ans, visited[curY][curX] - 1); // 가장 긴 시간을 계속 갱신

        for (int i = 0; i < 4; i++)
        {
            int newY = curY + dy[i];
            int newX = curX + dx[i];

            if (newX < 0 || newY < 0 || newX > width || newY > height)
            {
                continue;
            }
            if (map[newY][newX] == 'L' && !visited[newY][newX])
            {
                que.push({newY, newX});
                visited[newY][newX] = visited[curY][curX] + 1; // 새로운 위치가 정해지면 해당 위치에 +1
            }
        }
    }
}

int main()
{
    cin >> height >> width;

    for (int i = 0; i < height; i++)
    {
        cin >> map[i];
    }

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (map[y][x] == 'L')
            {
                bfs(y, x); // 최단거리이기 때문에 bfs
            }
        }
    }

    cout << ans << endl;
    return 0;
}