✔ 풀이를 위한 아이디어
- 그래프 (Graph) 이론과 너비 우선 탐색 (BFS)
- 메모리 초과와 시간 초과 방지하기
✔ 수정 전 코드 1 [메모리 초과]
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
queue = deque([])
if N == K:
print('0')
sys.exit()
queue.append(N+1)
if N - 1 >= 0:
queue.append(N-1)
queue.append(2*N)
count = 0
while queue:
ln = len(queue)
count += 1
for _ in range(ln):
tmp = queue.popleft()
if tmp == K:
print(count)
sys.exit()
queue.append(tmp+1)
if tmp - 1 >= 0:
queue.append(tmp-1)
queue.append(2*tmp)- 사실 풀이의 방향성은 맞았다. BFS를 활용하여 N-1, N+1, 2*N의 3가지 갈래로 계속해서 뻗어나가고, 그러다가 찾는 수에 도달하면 count 값을 출력하는 그런 풀이이다.
- 하지만 메모리 초과가 난 이유는 Queue에 넣는 값의 최대 범위를 제한하지도 않았으며, 이미 방문한 요소를 계속해서 Queue에 넣다보니 count가 커질 수록 Queue의 길이가 어마어마하게 커졌기 때문이다. 따라서 나는 이를 보완해서 코드를 다시 제출하였다.
✔ 수정 전 코드 [시간 초과]
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
queue = deque([])
if N == K:
print('0')
sys.exit()
visited = []
if N + 1 <= 100000:
queue.append(N+1)
visited.append(N+1)
if N - 1 >= 0:
queue.append(N-1)
visited.append(N-1)
if 2*N <= 100000:
queue.append(2*N)
visited.append(2*N)
count = 0
while queue:
ln = len(queue)
count += 1
for _ in range(ln):
tmp = queue.popleft()
if tmp == K:
print(count)
sys.exit()
if tmp + 1 <= 100000 and tmp + 1 not in visited:
queue.append(tmp+1)
visited.append(tmp+1)
if tmp - 1 >= 0 and tmp - 1 not in visited:
queue.append(tmp-1)
visited.append(tmp-1)
if 2*tmp <= 100000 and 2*tmp not in visited:
queue.append(2*tmp)
visited.append(2*tmp)- 코드가 굉장히 지저분하다. 풀기 싫었나보다.
- 수정 전 코드 1에서 달라진 점은 최대 범위인 10000을 설정했다는 것과, visted라는 배열을 활용해 이미 탐색한 지점은 다시 Queue에 넣지 않았다는 것이다.
- 그러나 "in visited"라는 코드로 인해 점점 길어지는 visited 배열을 매번 탐색해야 하고, 시간복잡도가 매우 높아져서 시간초과가 나게 된다.
✔ 수정 후 코드
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
MAX = 10 ** 5
dist = [0] * (MAX+1)
queue = deque([N])
while queue:
x = queue.popleft()
if x == K:
print(dist[x])
break
for nx in (x-1, x+1, 2*x): #위처럼 if문으로 나누기보다, for문을 이렇게 활용하면 코드가 깔끔하다.
if 0<= nx <= MAX and not dist[nx]:
dist[nx] = dist[x] + 1 # Dynamic Programming의 처리와 유사하다.
queue.append(nx)- 사실 더 고민했어야 하는데 도저히 방법을 모르겠어서 못참고 구글 찬스를 써버리고 말았다.
https://wook-2124.tistory.com/273 - 이 문제를 통해 내 잘못된 습관들 몇가지를 잡아낼 수 있는데, 아래와 같다.
- 배열의 탐색으로 인한 시간초과를 피하기 위해서는 위의 dist 배열처럼 값을 조회하는 식으로 풀어야 한다. 단순히 방문 여부만을 표시하는 것이 아니라 소요 시간까지도 계산할 수 있기 때문에 훨씬 효율적인 방법이다.
- 100000과 같은 값을 매번 쓰는 대신, MAX와 같은 변수에 넣어서 코드를 작성하면 깔끔해진다.
- N == K와 같은 특수한 경우를 따로 빼놓지 말고 한번에 처리할 수 있는 방법을 고민하자.
이 문제를 통해 배운 점들을 앞으로의 풀이에 꼭 적용하자!
✔ 관련 개념
- 메모리 초과와 시간 초과 방지하기
