[BOJ/2589번보물섬] c++ / BFS

문제

섬 안에서의 가장 먼 거리를 최단시간에 이동하는데 걸린 시간을 구하는 문제

-L이 섬(땅), W가 바다

-땅만 이동 가능

-한번 이동하는데 1시간 걸림

 

생각

처음에 보물이 숨겨졌다길래 대체 어디있는건가 고민했는데, 문제 읽어보니 그냥 가장 멀리 떨어진 두 지점 사이의 최단 거리를 구하는 거였음

* 런타임 에러 떴는데, 문자열을 잘못 입력 받은 것 같음 / 사실 뭐가 문제인지 모르겠음

 

문제풀이

1.vis 초기화 ( -1로 )

2.L이 나오면 BFS 탐색

3.기준 땅의 상하좌우에 방문하지 않은 땅이 있다면, 방문 표시 + 큐에 푸쉬 ( 기준칸 cnt + 1 )

4.cnt 값 반환

5.cnt값 비교해서 max 구하기

6.max 출력

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int N, M, m=0;
string board[51];
int vis[51][51];
int BFS(int x, int y) {
    memset(vis, -1, sizeof(vis));

    queue<pair<int, int>> Q;
    int cnt = 0;
    vis[x][y] = 0;
    Q.push({x, y});

    while(!Q.empty()) {
        pair<int, int> cur = Q.front(); Q.pop();
        
        for ( int dir = 0 ; dir < 4; dir++ ) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];

            if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
            if ( board[nx][ny] == 'W' || vis[nx][ny] > -1 ) continue;

            vis[nx][ny] = vis[cur.X][cur.Y] + 1;
            cnt = vis[cur.X][cur.Y] + 1;

            Q.push({nx, ny});
        }
    }
    return cnt;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for ( int i = 0; i < N; i++ )
        cin >> board[i];

    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( board[i][j] == 'L' ) {
                m = max(BFS(i, j), m);
            }
        }
    }

    
    cout << m;
}