BOJ 2589 · 보물섬

알고리즘 분류 : BFS  

BFS를 통해 맵을 탐색하면서 최단 거리를 구한다. 최단 거리 중에서 가장 긴 거리가 정답이다.

• 보물섬에서 이동할 때, 땅(L)에서 땅(L)으로만 이동할 수 있다. 물(W)로는 이동할 수 없다.
• BFS 탐색을 하면서 매번 이동 거리를 저장하고, 가장 큰 이동거리를 별도로 저장한다.
• 전체 맵에 있는 땅(L)의 개수만큼 BFS 탐색을 반복한다.
• BFS 탐색 결과로 나오는 이동 거리 중, 가장 큰 값을 정답으로 낸다.

---

C++ 소스코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct treasure {
    int x, y, d;
};

int n, m;
char a[51][51];
bool check[51][51];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

inline int max(int x, int y) { return x > y ? x : y; }

int bfs(int i, int j) {
    int dist = 0;
    queue<treasure> q;
    q.push({i, j, 0});
    check[i][j] = true;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, d = q.front().d;
        q.pop();
        for (int k=0; k<4; k++) {
            int nx = x+dx[k], ny = y+dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (check[nx][ny] || a[nx][ny] == 'W') continue;
            q.push({nx, ny, d+1});
            check[nx][ny] = true;
            dist = max(dist, d+1);
        }
    }
    return dist;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        scanf("%s", a[i]);
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (a[i][j] == 'L') {
                memset(check, false, sizeof(check));
                ans = max(ans, bfs(i, j));
            }
        }
    }
    printf("%d ", ans);
    return 0;
}

---

Python 3 소스코드

from collections import deque
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
check = [[False]*m for _ in range(n)]
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

def bfs(i, j):
    q = deque()
    q.append((i, j, 0))
    check[i][j] = True
    dist = 0
    while q:
        x, y, d = q.popleft()
        for k in range(4):
            nx, ny = x+dx[k], y+dy[k]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if check[nx][ny] is False and a[nx][ny] == 'L':
                q.append((nx, ny, d+1))
                check[nx][ny] = True
                dist = max(dist, d+1)
    return dist

ans = 0
for i in range(n):
    for j in range(m):
        if a[i][j] == 'L':
            check = [[False]*m for _ in range(n)]
            ans = max(ans, bfs(i, j))
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 2589