BOJ 13700 - 완전 범죄

문제

백준 온라인 저지 - 13700번

풀이 과정

시작 지점에서 목표 지점에 도달하는 최소 이동 횟수를 구하는 문제입니다.
문제 조건에서 경찰서에 중간에 방문하면 안된다는 조건이 있기 때문에 BFS 를 이용하여 탐색을 진행하기 전에
모든 경찰서 지점을 방문처리 해준 뒤 탐색을 수행하도록 해줍니다.

코드

import sys
from collections import deque


INF = 2e9


def bfs(start, goal):
    q = deque()
    visit = [0] * (N + 1)

    q.append([start, 0])
    visit[start] = 1

    for office in police_office:
        visit[office] = 1

    while q:
        here, click = q.popleft()

        if here == goal:
            return click

        for there in [here + F, here - B]:
            if 1 <= there <= N and not visit[there]:
                visit[there] = 1
                q.append([there, click + 1])

    return INF


def solution():
    press_count = bfs(S, D)

    return press_count if press_count != INF else 'BUG FOUND'


if __name__ == '__main__':
    N, S, D, F, B, K = list(map(int, sys.stdin.readline().split()))
    police_office = list(map(int, sys.stdin.readline().split()))

    answer = solution()
    print(answer)