[오답노트] 백준 #13549 숨바꼭질 3 (파이썬) : 0-1 BFS

Yongjun Park·2022년 3월 31일
0

PS(Problem Solving)

목록 보기
15/31

오늘의 한 마디
문제에서 0과 1의 가중치가 보이는 즉시 바로 0-1 BFS 쓰기

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

예제 출력 1

2

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.


발상

Try #1

처음 봤을 때는, 1로 만들기 문제랑 비슷한 다이나믹 프로그래밍 문제인 줄 알았다.
왜 아닌지는 아직도 정확히 모르겠지만, 문제의 알고리즘 분류를 보니 BFS였다.

그래서 BFS 최단 횟수 문제구나 싶었다.

# bfs 최단 횟수 문제

import sys

N, K = map(int, sys.stdin.readline().rstrip().split())

visited = [False] * 100001
time = 0
q = [N]
visited[N] = True
while q:
    q_cpy = q[:]
    q = []
    cnt = 0
    for case in q_cpy:        
        if case == K:
            cnt += 1
        if 0 <= case-1 <= 100000 and not visited[case-1]:
            q.append(case-1)
            visited[case-1] = True
        if 0 <= case+1 <= 100000 and not visited[case+1]:
            q.append(case+1)
            visited[case+1] = True
        if 0 <= case*2 <= 100000 and not visited[case*2]:
            q.append(case*2)
            visited[case*2] = True
    if cnt:
        print(time)
        print(cnt)
        exit()
    time += 1
        
# 순간이동을 하는 경우 0초 후에 2*X 위치로 이동???

당연히 샘플 입출력조차도 틀리게 나왔다.

겨우 BFS 최단 횟수 문제라면 왜 굳이 골드 5일까라는 생각을 잠깐 했지만, 이내 열심히 코딩을 했는데 아주 의외의 조건을 봐버렸다.

순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

예? 1초가 아니었구나... 그럼 순간이동은 무한번 할 수 있네...

가중치가 다른 상황에서 BFS를 쓸 수는 없었다.
그렇다고 다익스트라를 쓰자니 이게 정점과 간선으로 입력이 주어진 상황도 아닌데, 내가 뭘 기준으로 그래프를 만들지도 의문이었다.

Try #2

이 문제의 알고리즘 분류 제일 밑에는 0-1 너비 우선 탐색 이라는 말이 있었다.

https://nicotina04.tistory.com/168

우선 0-1 BFS를 사용하려면, 가중치가 0과 1 두개밖에 없어야 한다.
일반 BFS는 굳이 말하자면 가중치가 1밖에 없었다.
가중치가 0과 1 말고 여러가지로 나온다면, 다익스트라를 사용하도록 하자. (음수라면 벨만-포드)

알고리즘의 포인트는 다음과 같다.

  1. BFS 최단 횟수때 처럼 q_cpy를 굳이 만들 필요 없이, 일반 BFS를 해도 된다.
    • 왜냐하면 visited 배열에는 False/True를 저장하는 것이 아니라, 해당 정점(번호)까지 이동하는데 걸린 시간을 저장하기 때문이다. print(cnt)를 하는 게 아니라, print(visited[정점번호])를 하면 되기 때문에 굳이 while 루프를 비용 1에 한번만 돌게 할 필요는 없다.
  2. 가중치가 0인 이동(여기서는 2*X 연산)은 deque의 앞에 넣어야 한다!
    • 그렇게 해야 가중치가 0인 이동부터 전부다 BFS에서 다 계산하고 난 뒤에야 가중치가 1인 이동(X-1, X+1)을 계산하기 때문.

이것만 빼면 평범한 BFS와 다를게 없다.

그리고 DFS, BFS의 시간복잡도는 O(V+E)인데,
0-1 BFS 역시 O(V+E), 즉 선형시간에 끝나버린다! 미쳤다

풀이

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().rstrip().split())
visited = [-1] * 100001

q = deque([N])
visited[N] = 0
while q:
    now = q.popleft()
    if now == K:
        print(visited[now])
        exit()
    if 0 <= now-1 <= 100000 and visited[now-1] == -1:
        visited[now-1] = visited[now] + 1
        q.append(now-1)
    if 0 <= now*2 <= 100000 and visited[now*2] == -1:
        visited[now*2] = visited[now] + 0 	# Key Point
        q.appendleft(now*2) 				# Key Point
    if 0 <= now+1 <= 100000 and visited[now+1] == -1:
        visited[now+1] = visited[now] + 1
        q.append(now+1)
profile
추상화되었던 기술을 밑단까지 이해했을 때의 쾌감을 잊지 못합니다

0개의 댓글