오늘의 한 마디
문제에서 0과 1의 가중치가 보이는 즉시 바로 0-1 BFS 쓰기
- Baekjoon 문제 링크
- solved.ac > 문제 > CLASS 4에 수록된 문제입니다.
문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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 말고 여러가지로 나온다면, 다익스트라를 사용하도록 하자. (음수라면 벨만-포드)
알고리즘의 포인트는 다음과 같다.
- BFS 최단 횟수때 처럼
q_cpy를 굳이 만들 필요 없이, 일반 BFS를 해도 된다.- 왜냐하면
visited배열에는 False/True를 저장하는 것이 아니라, 해당 정점(번호)까지 이동하는데 걸린 시간을 저장하기 때문이다.print(cnt)를 하는 게 아니라,print(visited[정점번호])를 하면 되기 때문에 굳이 while 루프를 비용 1에 한번만 돌게 할 필요는 없다.
- 왜냐하면
- 가중치가 0인 이동(여기서는
2*X연산)은 deque의 앞에 넣어야 한다!- 그렇게 해야 가중치가 0인 이동부터 전부다 BFS에서 다 계산하고 난 뒤에야 가중치가 1인 이동(
X-1,X+1)을 계산하기 때문.
- 그렇게 해야 가중치가 0인 이동부터 전부다 BFS에서 다 계산하고 난 뒤에야 가중치가 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)