[알고리즘] 백준 2589

백준 2589번 보물섬

해결 과정 요약

bfs함수를 만들어주는데 visited배열을 거리로 최신화 시켜준다.
그리고 큐에 푸시하기 전에 ret값을 최신화 시켜준다.

v[ny][nx] = v[y][x] + 1;
ret = max(ret, v[ny][nx]);
q.push({ny, nx});

이러면 ret값은 두 곳 사이를 최단 거리로 이동하는 가장 긴 시간이 된다.
모든 육지에서 bfs를 실행해주고 ret-1을 출력한다.

풀이

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

int N,M;
string s;
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};
int m[50][50];
int v[50][50];
queue<pair<int,int>> q;
int ret = 0;

void reset(){
    fill(&v[0][0], &v[0][0] + 2500, 0);
}

void bfs(int sy, int sx){
    int y,x;
    v[sy][sx] = 1;
    q.push({sy, sx});
    while(q.size()){
        tie(y, x) = q.front(); q.pop();
        for(int i=0; i<4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= N || nx >= M || v[ny][nx] || m[ny][nx]) continue;
            v[ny][nx] = v[y][x] + 1;
            ret = max(ret, v[ny][nx]);
            q.push({ny, nx});
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for(int i=0; i<N; i++){
        cin >> s;
        for(int j=0; j<M; j++){
            if(s[j] == 'L') m[i][j] = 0;
            else m[i][j] = 1;
        }
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(m[i][j] == 0){
                bfs(i, j);
                reset();
            }
        }
    }
    cout << ret-1;
    
    return 0;
}

코멘트

전형적인 bfs문제..