[백준] 1697. 숨바꼭질 / python 파이썬

🚩 그래프탐색, BFS

 

thinking

1. fail (메모리초과)

처음 풀었을때는 N과 K의 범위가 커서 방문체킹을 인덱스로 접근하는 리스트로 안 만들고 딕셔너리로 만들었는데 메모리 초과가 났다.

구글링해보니, 이렇게 하면 방문했던 노드도 큐에 다시 넣어져서 그렇다고 한다.

---

⭐ 메모리 초과 발생 이유 : 

과거에 했던 값을 계속 처리하기 위해 큐에 값을 넣는 것 때문에 발생함.

ex. 10에서 갈 수 있는 노드: 9, 11, 20. but, 10까지 갈 수 있는 방법 엄청 많음. (9->10, 11->10, 5->10 ... )

 

2. success 😀

방문체킹 리스트를 인덱스로 접근해 100,001 개의 칸으로 만들어줬다. 칸이 10만개 있어도 아무런 상관없다.

괜히 숫자 커지고 for문 많아지면 쫄게된다.. 쫄지말자

이때 주의할건 19번째 줄에   if 0<=v<=100000:   조건을 설정해야한다 !

왜냐면 x가 가질 수 있는 값이 x-1, x+1, x² 인데 동생 위치의 범위가 0 ≤ K ≤ 100,000 이므로 x-1, x+1, x² 값들은 0~100,000 사이에 있어야 하기 때문이다.

 

코드

from collections import deque


def bfs(x):
    global res
    q = deque()
    q.append(x)
    visited = [0]*100001
    visited[x] = 1

    while q:
        x = q.popleft()
        if x == K:
            res = visited[x]-1
            return
        tmp = []  # 연결노드 담을 임시 리스트
        tmp.extend([x - 1, x + 1, 2 * x])
        for v in tmp:
            if 0<= v <=100000:  # 런타임에러(out of range) 방지용 범위설정
                if not visited[v]:  # 방문 안했으면 방문체크
                    visited[v] = visited[x]+1
                    q.append(v)
        tmp = []  # 초기화


N, K = map(int, input().split())  # N:수빈, K:동생
res = 0
bfs(N)
print(res)

 

 

한줄평

실버 1을 보고 실패각이라고 생각했는데 패쓰해서 행복하다 😀