[BOJ] 2589번: 보물섬

2589번: 보물섬

풀이

BFS로 맵을 다 돌아주면 된다. 최댓값을 찾아야 하기 때문에 시작점을 바꿔가면서 BFS 돌린다.

참고로 Max - 1을 결과로 출력해야 하는데 -1을 하는 이유는 visit_y_x= 1을 항상 하기 때문에 원하는 결과 값보다 항상 +1이 되기 때문이다.

코드

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

int w, h;
char Map[51][51] = {
    0,
};

int BFS(int y, int x)
{
    int MAX = 0;
    int visit[51][51] = {
        0,
    };
    const int dx[] = {0, -1, 1, 0};
    const int dy[] = {-1, 0, 0, 1};
    queue<pair<int, int>> q;

    q.push(make_pair(y, x));
    visit[y][x] = 1;

    while (!q.empty())
    {
        int xx = q.front().second;
        int yy = q.front().first;
        q.pop();

        if (visit[yy][xx] > MAX)
            MAX = visit[yy][xx];

        for (int i = 0; i < 4; ++i)
        {
            int nextX = dx[i] + xx;
            int nextY = dy[i] + yy;
            if (0 <= nextX && nextX < w && 0 <= nextY && nextY < h && visit[nextY][nextX] == 0 && Map[nextY][nextX] == 'L')
            {
                visit[nextY][nextX] = visit[yy][xx] + 1;
                q.push(make_pair(nextY, nextX));
            }
        }
    }

    return MAX;
}

int main()
{
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; ++i)
    {
        scanf("%s", Map[i]);
    }
    int Max = 0;
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if (Map[i][j] == 'L')
            {
                int rtn = BFS(i, j);
                if (rtn > Max)
                    Max = rtn;
            }
        }
    }
    printf("%d\n", Max - 1);
    return 0;
}