[BaekJoon] 2589 보물섬 :: monton

문제

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

풀이

각 섬의 가장 멀리 있는 땅간의 최소 거리를 구하는 문제 이므로 bfs 사용

가장 멀리 있는 땅간의 최소 거리라는 말이 어려운데 사실 두가지 조건만 지키면 된다

1) 한번 지나갔던 땅은 다시 지나가지 않을 것

2) 이쪽에서 저쪽으로 움직일때 최단 거리로 움직일 것

위의 두가지를 만족하는 가장 멀리 있는 땅을 구하는 방법이다

처음에 문제를 풀때 dfs로 풀어서 2)번을 만족하지 못하였다

그리고 모든 각각의 땅에서 bfs를 돌려야 해서 시간 초과로 걸릴 줄 알았는데

배열의 범위가 크지 않아서 무사 통과한듯 싶다

코드

#include <iostream>
#include <queue>
using namespace std;
 
int N, M,ans;
char arr[51][51];
int visit[51][51];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
void init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visit[i][j] = 0;
        }
    }
}
 
int main() {
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
 
    queue<int> qx, qy, qn;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 'L') {
                qx.push(i), qy.push(j), qn.push(0);
 
                while (!qx.empty()) {
                    int x = qx.front();
                    int y = qy.front();
                    int n = qn.front();
                    qx.pop(), qy.pop(), qn.pop();
 
                    ans = ans > n ? ans : n;
                    for (int i = 0; i < 4; i++) {
                        int nx = x + dir[i][0];
                        int ny = y + dir[i][1];
                        int nn = n;
 
                        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                        if (visit[nx][ny]||arr[nx][ny]=='W') continue;
                        
                        visit[nx][ny] = 1;
                        qx.push(nx), qy.push(ny), qn.push(nn + 1);
                    }
 
                }
                init();
            }
        }
    }
 
    cout << ans;
}