[백준 1697번] 숨바꼭질 (Python 파이썬) 풀이 방법

백준 1697번 <숨바꼭질> 문제 보기

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

백준 1697번 <숨바꼭질> 문제 풀이

from collections import deque

n, k = map(int, input().split())
dist = [0 for _ in range(100001)]

queue = deque()
queue.append(n)

while queue:
  value = queue.popleft()
  if value == k:
    print(dist[value])
  else:
    if 0 <= value-1 <= 100000 and dist[value-1] == 0:
      dist[value-1] = dist[value]+1
      queue.append(value-1)
    if 0 <= value+1 <= 100000 and dist[value+1] == 0:
      dist[value+1] = dist[value]+1
      queue.append(value+1)
    if 0 <= value*2 <= 100000 and dist[value*2] == 0:
      dist[value*2] = dist[value]+1
      queue.append(value*2)

 

• 접근 방식
  • 문제를 읽자마자 ‘엇, DP 같은데?’ 라는 생각이 들면서 고민없이 문제를 풀게 되었다. 바로 풀 수 있겠다는 설레는 마음에 제대로 된 설계도 않고(아이패드 꺼내기가 귀찮았던 것도 있고…ㅎ), 제출했더니 당연히! [시간 초과] 가 떴다. 아쉬운 마음이 컸지만, 진지하게 다시 고민해 보게 되었고 최단 시간을 찾는 문제이니 DFS나 BFS로 풀 수 있겠다고 생각했다. DFS로 모든 깊이까지 갔다오는 것 보다는 BFS로 처음 도달했을 때의 시간을 구하는 것이 더 효율적이라 생각했다.

 

• 코드 설명
  • N과 K의 범위가 0에서 100000이므로, 시간을 저장하는 dist를 100001개로 설정
  • deque를 이용해서 k를 처음 방문했을 때의 최단 시간을 찾아줄 수 있음
  • value-1 혹은 value+1 혹은 value*2 의 범위와 방문여부를 따져 최단 시간을 정해주고 deque에 넣어줌

 

• 후기
  • 다 풀고 나서 다른 분들 블로그에 풀이 검색해봤었는데 다들 for 반복문을 통해 if문 3개를 1개로 줄일 수 있었다 ㅠㅠ 나는 너무 노가다였다 ㅎㅎ….

 

 

if 0 <= value-1 <= 100000 and dist[value-1] == 0:
  dist[value-1] = dist[value]+1
  queue.append(value-1)
if 0 <= value+1 <= 100000 and dist[value+1] == 0:
  dist[value+1] = dist[value]+1
  queue.append(value+1)
if 0 <= value*2 <= 100000 and dist[value*2] == 0:
  dist[value*2] = dist[value]+1
  queue.append(value*2)

파이썬을 제대로 사용하지 못하고 노가다 형식으로 작성한 코드다. 다른 분들의 코드리뷰를 하면서 for 반복문의 특징을 익히고 코드를 고쳐볼 수 있었다. 고친 코드는 아래와 같다.

for i in (value-1, value+1, value*2):
	if 0 <= i <= 100000 and dist[i] == 0:
		dist[i] = dist[value]+1