백준 / 숨바꼭질 / 1697
Question
문제링크
Silver 1
Logic
기본 구조 : bfs
1. N은 K가 되기 위해서 3갈래 경우의 수로 나뉜다.
2n, n-1, n+1
- 나는 이 문제를 그래프의 관점에서 바라보았다. n에서 k까지 탐색하는 최단 거리의 그래프. 방법은 dfs와 bfs가 있다.
- 하지만, n의 자식중에는 n-1과 n+1이 있으므로, dfs를 택하면 무한 루프에 빠진다.
- 따라서, 방식은 bfs를 택하고, deque 대신 list와 pop(0)을 활용한다.
- 시간을 단축하기 위해 visited는 dictionary로 구현한다.
- 각 경우의 수에서 0미만, 100000초과, 방문한적이 있는 노드 일 경우 계산하지 않는다.
Code
from sys import stdin
from sys import stdin
n = 0
def bfs(n,k):
visited={i:0 for i in range(100001)}
queue = [(n,0)]
while queue:
n = queue.pop(0)
num=n[0]
if num == k : break
if num<0 or num>100000 : continue
if visited[num]==1 : continue
visited[num]=1
for nn in [num*2, num-1, num+1] : queue.append((nn,n[1]+1))
return n[1]
N,K = map(int,stdin.readline().rstrip().split())
print(bfs(N,K))
Author And Source
이 문제에 관하여(백준 / 숨바꼭질 / 1697), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@swany0509/백준-숨바꼭질-1697저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)