BOJ 13700 · 완전 범죄

알고리즘 분류 : BFS  

S부터 출발하여 D에 도착하는 최소 이동을 구하는 문제다. BFS를 이용하여 구하면 된다.

• S부터 시작하여 BFS 탐색을 진행한다.
• 현재 위치가 X라 할 때, 다음 위치는 X+F (→이동) 또는 X-B (←이동)이 된다.
• K개의 경찰서를 제외한 곳으로 이동하면서 최소 이동 횟수를 구하면 된다.

---

C++ 소스코드

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

int n, s, d, f, b, k;
int dist[100001];

void bfs() {
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == d) {
            printf("%d\n", dist[x]);
            return;
        }
        for (int nx : {x+f, x-b}) {
            if (nx < 1 || nx > 1e5) continue;
            if (dist[nx] == -1) {
                q.push({nx});
                dist[nx] = dist[x]+1;
            }
        }
    }
    printf("BUG FOUND\n");
}

int main() {
    memset(dist, -1, sizeof(dist));
    scanf("%d %d %d %d %d %d", &n, &s, &d, &f, &b, &k);
    while (k--) {
        int i;
        scanf("%d", &i);
        dist[i] = -2;
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

from collections import deque
n, s, d, f, b, k = map(int, input().split())
a = list(map(int, input().split())) if k else []

def bfs():
    q = deque()
    q.append(s)
    dist[s] = 0
    while q:
        x = q.popleft()
        if x == d:
            print(dist[x])
            return
        for nx in (x+f), (x-b):
            if 1 <= nx <= 1e5 and nx not in dist:
                q.append(nx)
                dist[nx] = dist[x]+1
    print("BUG FOUND")

dist = dict()
for i in range(k):
    dist[a[i]] = 0
bfs()

✓ Dictionary 자료형을 사용하여 방문 여부를 체크했다.

---

참고

• 백준 온라인 저지 : BOJ 13700