[백준 2589번] 보물섬

풀이

---

조건을 먼저 살펴보면 다음과 같다.

1. 보물은 육지에 있다. (L에 있다.)

2. 이동할 때는 육지로만 갈 수 있다.

3. 각 보물의 위치는 육지로 이동하였을 경우 가장 먼거리에 묻혀있다.

4. 이동 경로를 카운트 할때는 중복된 지점을 가거나 돌아가는 경우를 제외한다.

조건에 맞춰서 이동하기위해 BFS를 통해 이동할때마다 카운트를 세주면 되는것을 알 수 있다.

배열을 돌면서 육지일 경우 해당 지점에 1번 보물이 있다고 가정하고 해당 지점부터 BFS를 돌리면서 가장 멀리 있는 지점 (카운트 값이 가장 큰 지점)에 2번 보물이 있다고 가정한다.

MAP을 모두 돌면서 Max 카운트를 비교해서 저장하면 풀 수 있다.

즉, 육지일 경우 카운트가 가장 큰 값을 Max의 경우와 계속 비교하면서 돌아다니면 된다.

소스 코드

---

#include <iostream>
using namespace std;
 
char map[51][51];
int visit_map[51][51];
int ga, se;
int que_x[10001],que_y[10001];
int head_x, tail_x, head_y, tail_y;
int cnt, Max = 0;
 
void push(int x, int y) {
    que_x[tail_x++] = x;
    que_y[tail_y++] = y;
}
 
int pop_x() {
    return que_x[head_x++];
}
 
int pop_y() {
    return que_y[head_y++];
}
 
void visit_ini() {
    for (int i = 0; i < se; i++) {
        for (int j = 0; j < ga; j++) {
            visit_map[i][j] = 0;
        }
    }
}
 
void bfs() {
    while (head_x != tail_x) {
        int x = pop_x();
        int y = pop_y();
 
        if (x + 1 <= se - 1 && map[x + 1][y] == 'L' && visit_map[x+1][y] == 0) {
            push(x + 1, y);
            visit_map[x + 1][y] = visit_map[x][y]+1;
            cnt = visit_map[x][y] + 1;
        }
        if (x - 1 >= 0 && map[x - 1][y] == 'L' && visit_map[x - 1][y] == 0) {
            push(x - 1, y);
            visit_map[x - 1][y] = visit_map[x][y] + 1;
            cnt = visit_map[x][y] + 1;
        }
        if (y + 1 <= ga - 1 && map[x][y+1] == 'L' && visit_map[x][y+1] == 0) {
            push(x, y+1);
            visit_map[x][y + 1] = visit_map[x][y] + 1;
            cnt = visit_map[x][y] + 1;
        }
        if (y - 1 >= 0 && map[x][y-1] == 'L' && visit_map[x][y-1] == 0) {
            push(x, y-1);
            visit_map[x][y - 1] = visit_map[x][y] + 1;
            cnt = visit_map[x][y] + 1;
        }
    }
}
 
int main() {
    cin >> se >> ga;
    for (int i = 0; i < se; i++) {
        for (int j = 0; j < ga; j++) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < se; i++) {
        for (int j = 0; j < ga; j++) {
            if (map[i][j] == 'L') {
                head_x = 0; tail_x = 0; head_y = 0; tail_y = 0; cnt = 1;
                visit_ini();
                visit_map[i][j] = 1;
                push(i, j);
                bfs();
                if (Max < cnt) {
                    Max = cnt;
                }
            }
        }
    }
    cout << Max-1 << '\n';
    return 0;
}