[백준]보물섬

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

2589번: 보물섬

문제를 이해하면 별다른 어려움이 없는 문제였다.

육지마다 bfs를 실행해서 최단거리를 구해서 최단거리가 가장 긴 점을 찾는다.

처음에는 2차 배열로 육지마다 실행하려고 했지만, 그냥 입력을 받을 때 시작지점을 큐에 저장해서 실행했다.

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int N, M;
char map[50][50];
int isV[50][50];
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
queue<pair<int, int> >start_q;
queue<pair<int, int> >q;
int ans = -1e9;
 
int bfs(int r, int c) {
    memset(isV, -1, sizeof(isV)); //초기화
    q.push(make_pair(r, c));
    isV[r][c] = 0;
    int a = -1e9;
 
    while (!q.empty()) {
        int rr = q.front().first, cc = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = rr + dr[i], nc = cc + dc[i];
            if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
            if (map[nr][nc] == 'L' && isV[nr][nc] == -1) {
                isV[nr][nc] = isV[rr][cc] + 1;
                q.push(make_pair(nr, nc));
                if (isV[nr][nc] >= a) a = isV[nr][nc];
            }
        }
    }
    return a;
}
 
void solve() {
    while (!start_q.empty()) {
        int r = start_q.front().first, c = start_q.front().second;
        start_q.pop();
        int s = bfs(r, c);
        if (ans <= s) ans = s;
    }
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'L') start_q.push(make_pair(i, j));
        }
    }
    solve();
    printf("%d\n", ans);
    return 0;
}