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

백준의 보물섬(2589) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 맵에 2개의 보물이 있는데, 이 보물들은 "서로간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 2곳에 있다."

   맵은, 바다와 육지로 이루어져있으며, 육지에서 바다로 나아가지는 못한다.

   이 때, 보물이 있는 두 위치의 최단 거리로 이동하는 시간을 구하는 문제이다.

2. 어려워 보이지만 간단한 BFS/DFS 문제이다. 맵에서 육지를 나타내는 모든 정점에서 시작해서, BFS/DFS를 통해서

   육지인 곳으로만 계속 나아가면서 시간을 Count해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Answer;
char MAP[MAX][MAX];
int Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int BFS(int a, int b)
{
    int Tmp_Result = 0;
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        if (Tmp_Result < Visit[x][y]) Tmp_Result = Visit[x][y];
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if (Visit[nx][ny] == 0 && MAP[nx][ny] == 'L')
                {
                    Q.push(make_pair(nx, ny));
                    Visit[nx][ny] = Visit[x][y] + 1;
                }
            }
        }
    }
    return Tmp_Result;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 'L')
            {
                int R = BFS(i, j);
                Answer = Bigger(Answer, R);
                memset(Visit, 0, sizeof(Visit));
            }
        }
    }
 
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}