수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
from collections import deque
def bfs():
q = deque() # deque는 양쪽에서 입출력 가능
q.append(n) # q = deque([5])
while q:
x = q.popleft() # 처음 시작점은 x = 5, q = deque([])
if x == k:
print(dist[x])
break
for nx in (x - 1, x + 1, x * 2): # nx = 4, 6, 10
if 0 <= nx <= MAX and not dist[nx]:
dist[nx] = dist[x] + 1
q.append(nx) # q = deque([4, 6, "10"])
MAX = 10 ** 5 # 시간초과 안나게 수 제한
dist = [0] * (MAX + 1) # 이동하는 거리를 알기 위한 변수
n, k = map(int, input().split())
bfs()
풀이
전에 공부했던 BFS(Breadth-first Search) 방법으로 문제를 풀 수 있어요.
+ 참고로 bfs()는 def로 정의한 bfs함수를 실행시키는 거에요! () ← 요녀석이 실행 버튼입니다.
다음으로 bfs() 함수 코드를 살펴보기 전에 python에 내장되어있는 collections에서 deque를 import(수입)해왔어요. deque는 정보처리기사를 준비하면서 공부했던 개념인데요.
'''
key point 1
선형 구조로서의 자료구조로는 크게 Stack, Queue, Deque가 있는데 Stack은 LIFO(Last In First Out) 특성으로 가장 먼저 넣은 것이 맨 아래에 있기 때문에 가장 마지막에 나오고, 가장 마지막에 넣은 것이 맨 위에 있기 때문에 가장 먼저 나와요.
Queue의 특성은 FIFO(First In First Out)으로 가장 먼저 넣은 것이 쭉 큐를 통과해서 가장 먼저 나오게 되요. 그리고 Deque가 있는데, Queue와 Deque의 가장 큰 차이점은 Queue는 한 쪽에는 입력만 하고 반대쪽은 출력만 하는 반면, Deque는 양쪽 모두 입출력이 가능해요.
'''
자 그럼 이렇게 Deque의 특성까지 알아봤으니 bfs() 함수 코드를 자세히 풀이하면
q 변수를 deque()로 초기화하고 q.append(n)을 통해서
q = deque([5])
위와 같이 시작점을 deque에 추가해줬어요.
그리고 while 반복문을 사용해서 q가 정수일 때 계속해서 반복하게 하고
'''
key point 2
x 변수를 설정해서 deque에 들어있는 수를 left로 pop, 빼주었어요.
즉, leftpop()은 deque() 왼쪽에 있는 수를 빼주는 함수에요.
'''
다음으로 if문을 사용해서 x 변수인 수빈이의 위치가 동생이 있는 k와 같아진다면
얼마의 시간이 걸렸는지 print()하고 break로 while문을 멈춰요.
'''
key point 3
이제 가장 중요한 for문인데요.
for nx in (x - 1, x + 1, x * 2)에 x = 5를 대입시키면, nx = 4, 6, 10 이라는 값을 갖게 되요.
이것을 들여쓰기된 if문에서 0 <= 4, 6, 10 <= MAX 와(and)
(if) not dist[4, 6, 10], 즉 if문의 조건인 dist[4, 6, 10]이 거짓일 경우
제가 위의 not dist를 강조한 이유는 dist 변수로 설정한 것은 [0, 0, 0, ..., 0, 0]과 같이
0을 가지고 있는 리스트이기 때문에 dist[nx]의 값은 처음에는 무조건 0이 나올 수 밖에 없는데요.
이것을 다시 생각하면 dist[nx]는 0, 즉 언제나 False라는 점이에요!
때문에 if not dist[nx]는 조건이 언제나 거짓인 False이니 if문을 만족시키는 것이죠.
(이 부분이 이해가 잘 안가서 골똘히 머리 굴려봤습니다 ㅋㅋㅋㅋ)
반대로 if dist[nx]: 이렇게 되있었다면 dist[nx]는 0의 값인 False이니 if문의 조건이 거짓이어서
if문이 돌아가지 않겠죠??
'''
자 이렇게 if문까지 통과했으면 다 끝났어요..!!
dist[4, 6, 10] = dist[5] + 1 = 0 + 1 = 1
이렇게 dist[nx]의 값은 dist[x]에서 1씩을 더해주게 되는데요.
즉 dist[4, 6, 10]의 값 모두 1을 갖게 되고, deque에 들어가게 되는거에요.
q = deque([4, 6, 10])
이것을 그림으로 보면
출처: https://deepwelloper.tistory.com/75
위와 같이 하나하나씩 쭉 따라가는 것을 알 수 있어요.
여기서 힌트에 주어진 "수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다."를 따라가보면
댓글