[BOJ] #2589 보물섬

시간 제한	메모리 제한	정답 비율
1 초	128 MB	39.752%

 

2589번: 보물섬

해결방안

보물의 시작 점과 끝 점을 모르는 상태에서 가장 큰 육지의 끝과 끝의 최단거리를 구해야 하기 때문에 이중 for문을 돌리면서 모든 위치에 대해 BFS를 돌렸다. BFS를 돌릴 때 마다 현재가 가장 긴 거리라면 ans를 갱신하였고, 마지막까지 BFS탐색을 모두 마쳤다면 ans를 출력한다.

 

메모리	시간
2004 KB	84 ms

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define F(x,y,u,p) for(int x = 0 ; x<u; x++)for(int y = 0; y<p; y++)
typedef pair<int, int> p;
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, m, chk[55][55], ans;
char arr[55][55];
 
void bfs(int x, int y) {
    queue<p> q;
    q.push({ x, y });
    chk[x][y] = 0;
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = r + dx[i], nc = c + dy[i];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m || chk[nr][nc] >= 0 || arr[nr][nc] == 'W') continue;
            chk[nr][nc] = chk[r][c] + 1;
            if (ans < chk[nr][nc]) ans = chk[nr][nc];
            q.push({ nr, nc });
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
    }
    F(i, j, n, m) {
            if(arr[i][j] == 'L') bfs(i, j);
            memset(chk, -1, sizeof(chk));
    }
    printf("%d", ans);
    return 0;
}