[ BOJ / 파이썬 ] 1697 숨바꼭질

/  제출  1  /

 

from collections import deque

n, k = map(int, input().split())

array = [0] * 1000001
q = deque([n])
def bfs():
  while q:
    x = q.popleft()
    if x == k or array[k] != 0 :
      return array[k]
    if 0 <= x - 1:
      array[x-1] = array[x] + 1
      q.append(x-1)
    if x + 1 < 1000001:
      array[x+1] = array[x] + 1
      q.append(x+1)
    if x * 2 < 1000001:
      array[x*2] = array[x] + 1
      q.append(x*2)

print(bfs())

풀이는 올바른 것 같았는데 메모리를 고려 안 했습니다. 전체 케이스를 다 따지지 당연하게도 공간이 터졌습니다.

따라서 꼭 필요하게 업데이트하고자 했습니다.

 

 

 

/  제출  2  /

from collections import deque

n, k = map(int, input().split())

array = [0] * 1000001
q = deque([n])
def bfs():
  while q:
    x = q.popleft()
    if x == k or array[k] != 0 :
      return array[k]
    if 0 <= x - 1 and array[x - 1] == 0:
      array[x-1] = array[x] + 1
      q.append(x-1)
    if x + 1 < 1000001 and array[x+1] == 0:
      array[x+1] = array[x] + 1
      q.append(x+1)
    if x * 2 < 1000001 and array[x*2] == 0:
      array[x*2] = array[x] + 1
      q.append(x*2)

print(bfs())

다시 그림을 보면 아직 한 번도 할당 안 된 칸에만 재할당을 해주도록 변경했습니다.

왜냐하면 다시 q에 넣어도 그 값이 갈 수 있는 값은 이전과 달라지지 않기 때문입니다. 굳이 그 값을 다시 연산에 포함해서 필요 없는 계산이 수행되었던 것입니다.

 

더하여 원하는 k값에 거리가 차는 순간 종료조건을 설정해줬습니다.

그리고 n과 k가 같은 곳에 있다면 계산 없이 종료하게끔 했습니다.

 

BFS문제라는 것을 알지 못했으면 쉽게 떠올리지 못 했을 것 같은데 확실히 유형 파악이 되니까 풀이가 쉬웠습니다.

 

 

---

2022. 10. 06

 

다시 풀어보면서 다른 풀이 궁금해져서 찾아 봤는데

 

https://wook-2124.tistory.com/273

백준 알고리즘 | 1697 : 숨바꼭질 (Python / 파이썬)

 

이 분이 푸신 게 되게 깔끔하다.

저 두 달 전에 쓴 코드에서 같은 동작하는 if문 쓰는게 거슬렸는데 그걸 for in으로 해결하셨더라. 

최대값을 1000001 반복해서 안 쓰고 상수화 쓴 것도 훨씬 괜찮은 것 같다