💡문제 분석 요약
- n, k가 주어졌을 때 n이 k에게 가는 최단 시간을 측정한다.
- n은 n-1 , n+1 , 2*n 이렇게 3개의 방법으로만 움직일 수 있다.
💡알고리즘 설계
- 최단경로이긴 하지만, DP처럼도 풀 수 있어보였다. n을 2*(n-1) , 2*(n+1), 2*n 이렇게 3개중에 하나로 쭉 이어나가다보면 되지 않을까 했지만 실패했다.
- 결국, 최단경로를 찾는 매커니즘은 BFS이기 때문에 BFS로 접근해야했다.
💡코드
from collections import deque
n, k = map(int, input().split())
maxSize = 100000
visited = [0] * (maxSize + 1) # 각 위치를 방문했는지 여부 & 해당 위치까지 도달하는 데 걸린 시간
# 0이 아니니까 방문했다! 이거로 끝나는 게 아니고, 해당 숫자가 거기 인덱스까지 가는데 걸린 시간을 의미.
def bfs(start):
queue = deque()
queue.append(start)
while queue:
current = queue.popleft()
if current == k: # 탈출 조건
return visited[k] # value가 결국 time값. 즉, 해당 current까지 가는데 걸린 값이 value고, 시간을 의미.
for next in (current+1, current-1, current * 2): # 이동할 수 있는 경우는 이 3가지뿐
if 0 <= next <= maxSize and visited[next] == 0:
visited[next] = visited[current] + 1
queue.append(next)
print(bfs(n)) # visited[k]를 리턴
💡시간복잡도
- 3개의 비교를 for문에서 진행하지만 결국 O(N) 내로 끝나므로 O(N)이 될 것으로 보인다.
💡 틀린 이유
- BFS를 일차원에서 쓰는줄 모르고, DP처럼 접근했다가 틀렸다. 경험이 부족했다.
- list를 10만개 선언해도 되는지 감이 안와서 리스트 선언 안하고 어떻게 풀 수 있나 연구하다가 시간만 갔다.
💡 틀린 부분 수정 or 다른 풀이
- 분명 DP로도 풀 수 있을 것 같아서 찾아보았다.
def solution(n, k):
dp = defaultdict(lambda: float("inf"))
dp[n] = 0
for i in range(n):
dp[i] = n - i # n보다 작은 경우 초기화 (x-1로만 이동 가능)
for i in range(n + 1, k + 1):
if i % 2 == 0:
dp[i] = min(dp[i - 1] + 1, dp[i // 2] + 1)
else:
dp[i] = min(dp[i - 1] + 1, dp[(i + 1) // 2] + 2)
return dp[k]
💡 느낀점 or 기억할정보
- ★ ★ ★ ★ ★ visited로 방문, 안방문만 나타낸게 아니고 방문시 정보까지 나타낸 것이 인상깊었다. 그동안은 안방문일때 0, 방문이면 1 즉, 0만 아니면 방문한 것으로 인식했는데 방문한 그 때의 정보도 1개 value로 넘겨줄 수 있다는 것을 꼭 기억하자 !!!!!!!!!
- 10만개의 리스트를 초기화하는 것은 너무 크다고 생각해서 안하려고 했는데 상관 없었던 것이 조금 당황스러웠다.
- 애당초 BFS를 이차원에서만 사용하는 걸로 인식했던 것이 실수였다.
