BOJ 16469 · 소년 점프

알고리즘 분류 : BFS  

세 명의 사람이 한곳에 모이는 최단 거리와, 그 최단 거리의 수를 구해야 하는 문제다. 주어진 3명의 좌표를 큐에 집어넣고, 각각 BFS를 돌리면 된다.

• 3명의 사람을 0번, 1번, 2번이라고 하자.
• dist 배열은 이동 거리를 저장하고, 방문 여부를 체크한다.
• dist의 인덱스는 [X 좌표] [Y 좌표] [사람 번호] 이다. dist의 모든 값은 -1로 초기화해둔다.
• 큐에 0~2번 사람의 좌표를 모두 넣고, dist[X][Y][번호]를 0으로 초기화한다.
• BFS를 통해 완전 탐색을 하면, dist 배열에 각 사람의 이동 거리가 업데이트되어있다.
• dist배열을 N*M 순서로 탐색하면서 dist[X][Y][0], dist[X][Y][1], dist[X][Y][2]의 값이 모두 -1이 아닌 위치를 찾는다.
• 모두 -1이 아니라면, 3명이 만날 수 있는 장소이다.
• 이 장소 중에서 가장 최단 거리로 만날 수 있는 곳을 찾고, 같은 최단 거리가 존재한다면 수를 센다.

---

C++ 소스코드

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

struct grid {
    int x, y, z;
};

int n, m;
char a[101][101];
int dist[100][100][3];
queue<grid> q;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

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

int main() {
    memset(dist, -1, sizeof(dist));
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%s", a[i]);
    for (int i=0; i<3; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        q.push({x-1, y-1, i});
        dist[x-1][y-1][i] = 0;
    }
    bfs();
    int ans=1e9, cnt=0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            int x = dist[i][j][0], y = dist[i][j][1], z = dist[i][j][2];
            int k = max(max(x,y),z);
            if (min(min(x,y),z) != -1) {
                if (ans > k) {
                    ans = k;
                    cnt = 1;
                } else if (ans == k) {
                    cnt += 1;
                }
            }
        }
    }
    if (cnt) printf("%d\n%d\n", ans, cnt);
    else printf("-1\n");
    return 0;
}

---

Python 3 소스코드

from collections import deque
n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
dist = [[[-1]*3 for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()

def bfs():
    while q:
        x, y, z = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if a[nx][ny] == '0' and dist[nx][ny][z] == -1:
                q.append((nx, ny, z))
                dist[nx][ny][z] = dist[x][y][z]+1

for i in range(3):
    x, y = map(int, input().split())
    q.append((x-1, y-1, i))
    dist[x-1][y-1][i] = 0
bfs()
ans, cnt = 1e9, 0
for i in range(n):
    for j in range(m):
        k = max(dist[i][j])
        if min(dist[i][j]) != -1:
            if ans > k:
                ans = k
                cnt = 1
            elif ans == k:
                cnt += 1
if cnt:
    print("%d\n%d" % (ans, cnt))
else:
    print(-1)

---

참고

• 백준 온라인 저지 : BOJ 16469