[백준 1697번] 숨바꼭질

🎯 백준 - 1697.숨바꼭질

🤔 나의 풀이

📌 문제

- 백준 1697번 숨바꼭질
- BFS를 활용하는 문제이다.

📌 날짜

2020.02.11

📌 시도 횟수

7 try

💡 Code

from collections import deque

def bfs(x):
    visited = set()
    cnt = 0
    queue = deque([[x, cnt]])

    while queue:
        next = queue.popleft()
        cnt = next[1]
        if next[0] == k:
            return next[1]

        visited.add(next[0])
        if (next[0] - 1) not in visited and next[0] - 1 >= 0:
            queue.append([next[0] - 1, cnt + 1])
        if (next[0] + 1) not in visited and next[0] + 1 < 100001:
            queue.append([next[0] + 1, cnt + 1])
        if (next[0] * 2) not in visited and next[0] * 2 < 100001:
            queue.append([next[0] * 2, cnt + 1])


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

💡 문제 해결 방법

- BFS의 기본적인 틀을 조금 변형했다.
- 각 경로마다 count가 달라지는 것을 어떻게 구현할까 하다가,
차라리 처음부터 queue를 deque(list)로 만들어 queue의 요소가 
>> list = [현재 이동 위치, 몇 초 지났는지] 가 되도록 만들었다.
- cnt = next[1]를 통해 현재 값의 count를 매번 제대로 갱신해줄 수 있었다.
- 그리고 모든 경우에 대해 전부 다 BFS를 하게 되면 런타임에러가 뜨므로,
(다음에 큐에 삽입할 숫자가 유효한 수인지 & 이미 방문하지는 않았는지)를 고려했다.

💡 새롭게 알게 된 점

⭐in 시간복잡도 비교
- set의 in : O(1)
- list의 in : O(N)

❌ (한번에 맞추지 못한 경우) 오답의 원인

😂 런타임 에러가 엄~청 많이 발생했다. 그 원인으로는...

1. visited를 해주지 않아서 런타임 에러가 났다.
이전에 검사한 숫자가 또 나오는 경우 다시 탐색할 필요가 없었다.

2. next-1/next+1/next*2 가 범위를 벗어나는 경우를 고려하지 않았다.
>> next[0] - 1 >= 0
>> next[0] + 1 < 100001
>> next[0] * 2 < 100001
이걸 처리해주지 않았다.

3. visited를 set으로 만들지 않았다! 검색해보니까..
-------------------------
- set의 in : O(1)
- list의 in : O(N)
-------------------------
이라고 한다. 그래서 시간초과가 났나부다😭
지금이라도 알아서 다행이다.