BOJ 14940 · 쉬운 최단거리

알고리즘 분류 : BFS  

맵에 주어진 목표지점에서 각 지점에 대한 거리를 구하는 문제다. BFS를 통해 각 점에 대한 최단 거리를 모두 출력하면 된다.

• N*M 사이즈의 맵에서 목표지점(2)로부터 각 지점까지의 최단 거리를 구한다.
• 벽(0)으로는 이동할 수 없다.

---

C++ 소스코드

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

struct grid {
    int x, y;
};

int n, m, sx, sy;
int a[1000][1000];
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};

void bfs() {
    queue<grid> q;
    q.push({sx, sy});
    a[sx][sy] = 2;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; 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] == 1) {
                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] == 2) sx = i, sy = j;
        }
    }
    bfs();
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            int d = a[i][j];
            printf("%d ", d ? d-2 : 0);
        }
        printf("\n");
    }
    return 0;
}

---

Python 3 소스코드

from sys import stdin, stdout
from collections import deque
input = stdin.readline
print = stdout.write

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

def bfs():
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < m and a[nx][ny] == 1:
                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] == 2:
            q.append((i, j))
            a[i][j] = 2
            break
bfs()
for i in range(n):
    for j in range(m):
        d = a[i][j]
        print("%d " % (d-2 if d else 0))
    print("\n")

---

참고

• 백준 온라인 저지 : BOJ 14940