BOJ 17086 · 아기 상어 2

알고리즘 분류 : BFS  

아기 상어와의 거리를 구하는 문제다. BOJ 17086번 아기 상어와는 완전히 다른 문제다. 각 좌표에서 아기 상어와 떨어진 거리가 안전거리이며, 안전거리의 최댓값을 구해야 한다.

• 맵을 입력받으면서 상어의 위치(1)가 주어지면, 큐에 모두 집어넣는다.
• 각 상어 위치부터 BFS 탐색을 하면서, 빈칸(0)이면 이동하면서 이동거리를 맵에 저장한다.
• 맵을 완전 탐색한 후, 맵에 저장된 최댓값이 안전거리의 최댓값이 된다.
• 거리를 1부터 시작했기 때문에, 정답은 위에서 구한 최댓값에 1을 빼야 한다.

✓ 1번 예제 테스트케이스를 설명하는 그림이다. 각 상어 위치(초록색)부터 BFS를 시작하면, 오른쪽 상태처럼 된다.

---

C++ 소스코드

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

struct shark {
    int x, y;
};

int n, m, ans;
int a[50][50];
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
queue<shark> q;

void bfs() {
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        for (int k=0; k<8; k++) {
            int nx = x+dx[k], ny = y+dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (!a[nx][ny]) {
                q.push({nx, ny});
                a[nx][ny] = a[x][y]+1;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j]) q.push({i, j});
        }
    }
    bfs();
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (ans < a[i][j]) ans = a[i][j];
        }
    }
    printf("%d\n", ans-1);
    return 0;
}

---

Python 3 소스코드

from collections import deque

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

def bfs():
    while q:
        x, y = q.popleft()
        for k in range(8):
            nx, ny = x+dx[k], y+dy[k]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not a[nx][ny]:
                q.append((nx, ny))
                a[nx][ny] = a[x][y]+1

for i in range(n):
    for j in range(m):
        if a[i][j]:
            q.append((i, j))
bfs()
print(max(map(max, a))-1)

---

참고

• 백준 온라인 저지 : BOJ 17086