[백준 2589] 보물섬

[백준 2589] 보물섬

문제 링크

#include "header.h"
using namespace std;
char map_[51][51];
int visit[51][51];
int L, W;
int ans;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

void input() {
    cin >> L >> W;
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map_[i][j];
        }
    }
}
void check() {
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < W; j++) {
            if(visit[i][j]){
                ans = max(ans, visit[i][j]);
            }
        }
    }
}
void bfs(int x, int y) {
    queue<pair<int, int>> q;

    q.push({x, y});
    visit[x][y] = 1;
    int cnt = 1;

    while (!q.empty()) {
        int top_x = q.front().first;
        int top_y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];

            if (visit[nx][ny] || map_[nx][ny] == 'W' || nx < 0 || ny < 0 || nx >= L || ny >= W) continue;

            visit[nx][ny] = visit[top_x][top_y] + 1;
            q.push({nx, ny});
        }
    }
}
void solve() {
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < W; j++) {
            if (map_[i][j] == 'L') {
                bfs(i, j);
                check();
                memset(visit, 0, sizeof(visit));
            }
        }
    }
}
int main() {
    input();
    solve();
    cout << ans - 1 << endl;
    return 0;
}

• 모든 L에서 bfs를 돌린 후, 거리를 업데이트 해준다. visit[nx][ny] = visit[top_x][top_y] + 1
• bfs 종료 후, 가장 먼 거리를 구하고 -1을 해준 것이 답이다. (1부터 시작했기 때문에)