[BOJ] 1697 : 숨바꼭질 - 파이썬(Python)

문제 해석

---

바로 전에 풀었던 문제와 똑같은 BFS를 돌릴 때 depth를 포함해 튜플 형태로 덱에 append시킨 후 탐색을 진행하는 문제였다.

 

 

문제 풀이

---

import sys
from collections import deque


N, K = map(int, sys.stdin.readline().split())

deq = deque()
cnt = 0
deq.append((N, cnt))


while deq:
    N, cnt = deq.popleft()
    if N != K:
        deq.append((N - 1, cnt + 1))
        deq.append((N + 1, cnt + 1))
        deq.append((N * 2, cnt + 1))
    else:
        result = cnt
        break


print(result)

 

우선 테스트 케이스가 하나 뿐이지만 직관적으로 떠오르는대로 짠 코드이다.

 

이렇게 해서 N이 K가 되었을 때의 depth값 cnt를 result에 할당해서 출력하면 도달할때까지 몇초가 걸렸는지를 알 수 있다.

 

하지만 메모리 초과가 났기 때문에 문제에서 원하는 조건과 그에 맞는 코드가 무엇인지를 찾아보았다.

 

import sys
from collections import deque


N, K = map(int, sys.stdin.readline().split())

max = 100000
visited = [0] * (max + 1)

deq = deque()
deq.append(N)

while deq:
    x = deq.popleft()
    if x == K:
        print(visited[x])
        break
    for nx in (x - 1, x + 1, x * 2):
        if 0 <= nx <= max and not visited[nx]:
            visited[nx] = visited[x] + 1
            deq.append(nx)

 

문제에서 주어진 변수의 범위에 맞게 코드를 짜거나 시간초과를 그다지 경험해본 적이 없어서 많이 당황했다.

 

우선 N의 범위가 100000 이기 때문에 max에 100000을 할당해주고 방문을 확인할 리스트 visited를 max+1의 길이로 선언했다.

 

그리고 덱에 새로 방문할 노드를 삽입하는 부분에서도 새로 방문할 노드가 0부터 max 사이의 숫자인지를 확인한 후에 덱에 append 시켰다.

 

단순히 모든 경우의 수를 다 덱에 삽입해서 탐색을 돌리는 문제가 아니라

 

조건에 맞는 경우의 수만 제한해서 탐색하게 조건을 거는 문제에도 익숙해져야 다른 문제를 풀때도 그런 부분까지 생각해보고 문제를 풀다 막혔을때 방법을 생각해낼 수 있을것 같다.