첫 번째 풀이
from collections import deque
import sys
input = sys.stdin.readline
MAX = int(10e5)
N, M = map(int, input().split())
visited = [0 for _ in range(MAX+1)]
# print(visited)
answerTime = 0
answerList = []
def bfs():
global answerTime
global answerList
queue = deque()
queue.append((N, 0))
while queue:
# input()
X, findTime = queue.pop()
# print("X = ", X)
visited[X] = 1
if X == M:
# print("찾았다 !! ")
answerTime = findTime
answerList.append(findTime)
continue
if 0 <= 2*X <= MAX and visited[2*X] == 0:
queue.appendleft((2*X, findTime))
if 0 <= X-1 <= MAX and visited[X-1] == 0:
queue.appendleft((X-1, findTime+1))
if 0 <= X+1 <= MAX and visited[X+1] == 0:
queue.appendleft((X+1, findTime+1))
if X+1 > MAX:
continue
# print(queue)
bfs()
if N==M or len(answerList) == 0:
print(0)
else:
print(min(answerList))
# print(answerList)
정답은 맞지만 채점하는데 한참 걸린다. 시간초과가 뜨지 않을까 계속 조마조마 했다.
두 번째 풀이
from collections import deque
import sys
input = sys.stdin.readline
MAX = int(10e5)
N, M = map(int, input().split())
visited = [0 for _ in range(MAX+1)]
# print(visited)
answerTime = 0
answerList = []
def bfs():
global answerTime
global answerList
queue = deque()
queue.append((N, 0))
while queue:
# input()
X, findTime = queue.pop()
# print("X = ", X)
if X == M:
# print("찾았다 !! ")
answerTime = findTime
answerList.append(findTime)
continue
if 0 <= 2*X <= MAX and visited[2*X] == 0:
visited[2*X] = 1
queue.append((2*X, findTime))
if 0 <= X-1 <= MAX and visited[X-1] == 0:
visited[X-1] = 1
queue.appendleft((X-1, findTime+1))
if 0 <= X+1 <= MAX and visited[X+1] == 0:
visited[X+1] = 1
queue.appendleft((X+1, findTime+1))
if X+1 > MAX:
continue
# print(queue)
bfs()
if N==M or len(answerList) == 0:
print(0)
else:
print(min(answerList))
# print(answerList)
시간이 한참이나 줄었다.
차이점 (BFS - 최적화)
먼저 이 문제는 두 가지 방법으로 풀 수 있다고 한다. 첫 번째 방법은 최적화된 BFS 이고 두 번째 방법은 다익스트라를 이용하는 방법이다.
나는 BFS로 풀었다. (숨바꼭질 1 2를 풀고 와서 그런 걸수도..)
Edge의 weight가 다르면 BFS 로 풀 수 없고 다익스트라로 풀어야 한다. 그게 아니라면 첫 번째 풀이대로 한참 걸려서 정답이 나올 수 있다.
두 코드에서 가장 큰 차이점은 바로 방문체크를 하는 시점이다. 나는 지금까지 큐에서 원소를 빼왔을 때!! (원소 하나 빼와서 가지고 놀기 직전에) 방문 체크를 해주고 작업을 시작했다.
그럼 어떤 문제가 생기느냐
입력이 1로 들어왔다고 쳐보자 +1, -1, X2 세가지 방법이 있다고 했을 때
제일 처음에 1을 pop 하고 3번 push한다.
+1 일 때 => 2, 2 push
queue = [2]
-1 일 때 => 0, 0 push
queue = [2, 0]
X2 일 때 => 2, 2 push
queue = [2, 2, 0]
pop 할 때 방문 체크를 해주기 때문에 2가 2번이나 들어간다.
똑같이 2로 오는 건데(어떻게 해서든, 어떤 방법을 쓰던 2로만 오면 되는건데) 중복으로 해줄 필요가 없다는 얘기다.
숫자가 작을 땐 문제가 되지 않지만 숫자가 어마무시하게 커진다면?
=> queue 에 중복된 숫자가 어마무시하게 많아질거고
=> 연산 시간이 오래 걸린다. (첫 번째 풀이 방식 => 2316ms)
push 해줄 때 방문 체크를 해버리면 중복이 생기지 않는다. 시간이 훨씬 줄어든다. => 252ms
하지만 이 방법은 숨바꼭질 2와 같이 가능한 모든 경우를 체크해야 하는 경우엔 성립되지 않는다. 어떻게 해서든 가기만 하면 되는 경우엔 중복이 되어도 괜찮기 때문이다(중복이 되어야만 한다)
방문 체크를 해주는 위치와 더불어 또 한가지 중요한 게 있는데 바로 곱하기 if 문을 제일 위로 끌어올리는 것이다.
이번 문제에서는 최단 시간을 구해야 한다. 곱하기로 갈 수 있는 경우엔 먼저 방문해서 방문 체크를 해놓아야 한다.
1에서 3으로 가고 싶은 경우를 예로 들면
원래의 방식(+1, -1, X2)로 했을 땐 (똑같이 BFS 동작)
1 -> (+1) -> 2 -> (+1) -> 3
으로 총 3번이 걸리고 이를 배열에 집어넣는다.
하지만 X2를 제일 위로 끌어올려 X2, +1, -1 로 하면
1 -> (X2) -> 2 -> (+1) -> 3
으로 총 2번이 걸리고 이를 배열에 집어넣는다.
무조건 전부 돌기 때문에 어떻게든 정답은 나오지만 시간의 차이가 확실하다.
결론은
방법의 수(숨바꼭질 2에서의 cnt)는 필요없고 최단 시간이 얼마인지만 알면 될 경우엔 push 하면서 방문 체크를 한다 => 큐에 중복되는 원소가 없다.
