보물섬

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
// 0107 ~ 0127
// 1) 모든 육지 좌표에 대해 BFS수행해서 최대값 뽑기
int N, M, ans;
char board[55][55];
int cost[55][55];
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
vector<pair<int,int>> land;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 'L')
                land.push_back({i,j});
        }
    for(int n=0;n<land.size();n++)
    {
        auto c = land[n];
        for(int i=0;i<N;i++)
            fill(cost[i], cost[i]+M, 1e9);
        queue<pair<int,int>> q;
        q.push(c);
        cost[c.first][c.second] = 0;
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int nr = cur.first + dr[dir];
                int nc = cur.second + dc[dir];
                if(nr<0 or nc<0 or nr>=N or nc>=M) continue;
                if(cost[nr][nc] != 1e9 or board[nr][nc] == 'W') continue;
                q.push({nr,nc});
                cost[nr][nc] = cost[cur.first][cur.second] + 1;
                ans = max(ans,cost[nr][nc]);
            }
        }
    }
    if(ans == 1e9) ans = 0;
    cout << ans;
    return 0;
}

• 핵심
  • 모든 육지의 좌표에서 연결된 육지간 최장 거리를 구해서 최대길이를 찾아야 한다