[Python] 백준/BOJ 13700번: 완전 범죄 (Silver 1)

💻 Problem

문제 보러 가기

 

홍익대학교 근처에 있는 오락실에 새로운 게임이 들어왔다. 이 게임을 클리어하려면 방금 막 금은방을 턴 마포구 대도 X가 되어 아무에게도 들키지 않고 X의 집에 무사히 도착해야 한다. 게임은 오직 좌우 버튼 두 개로만 진행되고 규칙은 아래와 같다.

1. 마포구의 모든 건물은 일렬로 나열되어 있고 각 건물에는 1번부터 N번까지 번호가 지정되어 있다. 마포구에는 K개의 경찰서가 있고 경찰 내부에는 이미 X의 얼굴이 알려졌다.
2. 게임이 시작될 때 X는 막 범행을 끝내고 금은방 S 안에 있다.
3. X는 자신의 집 D에 마포구를 떠날 수 있는 비밀 통로를 만들어놓았다. 따라서 경찰에게 발각되지 않고 무사히 집으로 돌아가야 한다.
4. 좌(←) 버튼을 누르면 후방으로 달리고, 우(→) 버튼을 누르면 전방으로 달린다. X는 마포구 내에서만 이동할 수 있으며, 자신이 오랜 연구 끝에 알아낸 이동 방식을 맹신하여 오직 그 방식으로만 이동한다.
5. X의 달리기는 남에게 얼굴이 보이지 않을 정도로 매우 빠르다. 현재 X가 a번 건물 안에 있다고 가정하면, 밖으로 나와 전방으로 달려 a+F번 건물 안으로 이동하거나, 후방으로 달려 a-B번 건물 안으로 이동할 수 있다. 단, X의 달리기는 자신도 주체할 수 없을 만큼 빨라서 중간에 멈출 수 없다.
6. X는 한 번 달리면 너무 힘들어 건물 안에서 10초 동안 휴식을 취해야 한다. 이때 X가 경찰서 안에서 휴식을 취할 경우, 그는 집에 돌아가지 못하고 체포된다.

이 게임은 아직 베타 버전이라 무사히 집으로 가는 방법이 없는 버그도 존재한다.

지언이의 취미는 오락실 게임을 누구보다 빠르게 클리어하는 것이다. 그래서 대도 X가 무사히 집에 도착할 수 있는 여러 방법 중에서도 좌우 버튼을 가장 최소로 눌렀을 때의 횟수를 알고 싶다.

마포구 건물의 개수 N, 털린 금은방 S, 대도 X의 집 D, 앞으로 한 번에 달릴 수 있는 건물 수 F, 뒤로 한 번에 달릴 수 있는 건물 수 B, 마포구 경찰서의 개수 K, 각 경찰서의 건물 번호 l1, l2, …, lK가 주어질 때 대도 X가 무사히 집에 도착하기 위해 버튼을 눌러야 하는 최소 횟수를 출력하는 프로그램을 작성해라.

만약 집으로 가는 방법이 없는 경우를 발견했다면 이 데이터를 게임 회사에 알리기 위해 “BUG FOUND”를 출력한다.

• 첫째 줄에 N, S, D, F, B, K가 주어지고, K > 0인 경우에는 둘째 줄에 경찰서의 위치 l1, l2, …, lK가 주어진다. (1 ≤ S, D ≤ N ≤ 100000, 0 ≤ F, B ≤ 100000, 0 ≤ K ≤ N/2, S ≠ D ≠ l) 

 

💡 Approach

1차원 배열 bfs 문제이다.

 

시작점은 S, 도착점은 D이다.

대도 X는 +F만큼 이동하거나 -B만큼 이동할 수 있다.

만약 이동하려는 칸이 경찰서면 그 칸으로 이동할 수 없다.

도착점까지 가는 최소 이동 횟수를 구하는 문제이다.

 

처음에 보자마자 bfs 생각나서 bfs로 풀었는데 next not in police를 써서 시간 초과가 떴다.

이땐 생각 못하고 그냥 bfs가 아닌가.. 하고 그리디 쪽으로 파봤다. (이러지 말았어야..)

 

시작점보다 도착점이 앞에 있으면 무조건 앞으로 가다가 앞으로 못가면 한 번 뒤로 가는 식,

시작점보다 도착점이 뒤에 있으면 무조건 뒤로 가다가 뒤로 못가면 한 번 앞으로 가는 식.. 으로 했다.

이러면 모든 경로를 탐색할 수 없다는 거 아는데 이땐 최단 거리는 무조건 이렇게 나오지 않나 싶었다.

예제도 다 맞았었고..

그치만 4%에서 틀려서.. 반례를 엄~~~청 찾아보는데 ㅠㅠ 못찾겠는 거다..

 

그러다가 다시 bfs로 돌아와서 경찰서 미리 방문 처리하는 걸로 바꿨더니 통과했다.

그리고 bfs 코드랑 그리디 코드에 예제 넣어보면서 반례 찾고 있는데.. 진짜 다 똑같이 나오는 거다.. ㅠㅠ

 

내가 S랑 D를 너무 멀게 설정했나보다..

둘이 가까울 때 반례를 찾을 수 있었다..

10 8 5 1 2 1 9 ans = 3

10 1 3 4 1 1 9 ans = 3

50 10 11 4 1 3 1 20 25 ans = 4

10 1 2 4 1 1 9 ans = 4

이 반례를 그리디 코드에 넣으면 모두 BUG FOUND가 출력된다.

ㅠㅠ 왜 그리디로 최단 거리가 가능하다고 생각했었을까

 

✏️ Solution

import sys
from collections import deque
input = sys.stdin.readline

def play():
    queue = deque([(S, 0)])
    visited[S] = True

    while queue:
        current, cnt = queue.popleft()
        
        # 집에 도착하면 종료
        if current == D:
            return cnt

        # 앞으로 이동하거나 뒤로 이동
        for next in (current + F, current - B):
            if 0 < next <= N and not visited[next]:
                visited[next] = True
                queue.append((next, cnt + 1))

    return "BUG FOUND"

# 마포구 건물의 개수 N, 털린 금은방 S, 대도 X의 집 D, 앞으로 한 번에 달릴 수 있는 건물 수 F, 뒤로 한 번에 달릴 수 있는 건물 수 B, 마포구 경찰서의 개수 K
N, S, D, F, B, K = map(int, input().split())
# 마포구 경찰서의 건물 번호
police = list(map(int, input().split()))
visited = [False] * (N + 1)

for p in police:
    visited[p] = True

print(play())

• 시간복잡도
  • 노드 수: N
  • 간선 수: 2N (앞/뒤 2개 이동)
  • 노드 수 + 간선 수 = 3N = 3 * 10^5

 

처음에 bfs로 풀었는데 시간 초과였던 건 next not in police 때문이었다.

next not in police 연산을 수행할 때는 O(K)가 걸리는데 미리 방문 처리를 하면서 O(1)이 되어 통과할 수 있었다.

 

혹은 police를 list가 아닌 set으로 하면 next not in police 연산을 하더라도 시간 안에 통과할 수 있다.

set은 해시 테이블 기반이라 원소 존재 여부 확인이 O(1)이기 때문이다.

이걸 알면서도 처음에 set으로 바꿀 생각을 못했는데 다음엔 이 점을 잘 떠올려야겠다..

 

시간 초과한 제출은 처음에 푼 bfs 코드, 틀린 문제는 그리디로 푼 코드, 맞은 코드는 다시 bfs로 푼 코드이다.

더 먼저 푼 게 경찰서 방문 처리를 미리 해준 거고 가장 마지막에 제출한 게 맨 처음 코드에서 경찰서 list만 set으로 바꾼 코드이다.