[Jungol] 정올 1462 보물섬

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=734&sca=30

 Input 

5 7

WLLWWWL

LLLWLLL

LWLWLWW

LWLWLLL

WLLWLWW

 

 Output 

8

- 육지가 바다로 나눠져 있다면 육지간 이동은 불가능합니다.

- 연결된 육지에서 최단거리로 이동하되 가장 멀리 있는 곳의 거리를 찾는 문제입니다. → BFS

- 육지(L)에 해당하는 모든 지점에서 이동할 수 있는 가장 먼거리를 찾습니다. (초기화 유의)

  즉, 『L』로 표시된 모든 지점을 출발점으로 BFS 탐색하며 가장 멀리 도달한 거리를 찾습니다.

- 특정 위치 (x, y)에서 출발 했을 때, visited[i][j] = (i, j)에 도달하기 위한 최단 거리

   BFS 탐색이 끝난 후 매번 visited[][]에 저장된 값 중 최대값을 구합니다.

---

#include <stdio.h>
 
inline int max(int A, int B) { if (A > B) return A; return B; }
const int INF = 2e9;
const int MAX_NM = 50 + 5;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
int N, M, ans;
char map[MAX_NM][MAX_NM];
int visited[MAX_NM][MAX_NM];
struct Node{
    int x, y, cost;
}que[MAX_NM * MAX_NM * 4];
int fr, re;
 
void init() {
    fr = re = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            visited[i][j] = INF;
        }
    }
}
 
void BFS(int x, int y) {
    init();
    que[re++] = {x, y, 0};
    visited[x][y] = 0;
    while (fr < re) {
        Node cur = que[fr++];
        
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
 
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                continue;
            if (map[nextX][nextY] == 'W')
                continue;
            int nextCost = cur.cost + 1;
            if (visited[nextX][nextY] <= nextCost)
                continue;
            
            visited[nextX][nextY] = nextCost;
            que[re++] = { nextX, nextY, nextCost };
        }
    }
 
    // visited[][]에 저장된 값 중 최대값(최단거리 중 가장 먼 곳)
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (visited[i][j] != INF)
                ans = max(ans, visited[i][j]);
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i) {
        scanf("%s", map[i]);
    }
 
    // 육지(L)에 해당하는 지점
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (map[i][j] == 'L') {
                BFS(i, j);
            }
        }
    }
    
    printf("%d\n", ans);
}