[Python] 백준 1697: 숨바꼭질

문제 풀이 방법은 엘리베이터 문제인 스타트링크 문제와 유사하다.
하지만 이 문제 역시 틀렸다.

정답률이 25%밖에 안되는 나에겐 극악의 난이도였다. 혼자 힘으로 풀기 역시 실패였다...🥲

처음에 내가 풀이한 방식은 다음과 같다.

from collections import deque

n, k = map(int, input().split())
visited = {}
def bfs(s):
    q = deque()
    q.append(s)
    visited[s] = 0
    while q:
        cur = q.popleft()
        if cur == k:
            return visited[k]
        for i in (cur+1, cur-1, cur * 2):
            if i not in visited: 
              visited[i] = visited[cur] + 1
              q.append(i)
print(bfs(n))

가장 빠른 시간(최소 도달시간)을 구하는 문제이므로 BFS로 접근했다.
이 코드는 거의 확실히 정답이라고 생각했는데 계속 메모리 초과가 발생했다.
정답률이 낮은 이유 역시 이 때문이라고 생각한다.

이런 점에서 보면 visited에 set이나 dictionary를 사용하는 것이 그리 좋지만은 않은 것 같다. 이 두 자료형을 사용하다가 메모리 초과가 된 경험이 꽤 많다..

그럴 땐 메모리가 상대적으로 많이 필요한 set, dictionary보다는 list를 사용하는 것이 나은 것 같다.

from collections import deque

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

MAX = 10 ** 5
visited = [0] * (MAX + 1)
def bfs(s):
    q = deque()
    q.append(s)

    while q:
        cur = q.popleft()
        if cur == k:
            return visited[k]
        for i in (cur+1, cur-1, cur * 2):
            if 0 <= i <= MAX and not visited[i]: 
              visited[i] = visited[cur] + 1
              q.append(i)
print(bfs(n))

visited로 사용하던 dict를 list로 수정했다.
이를 수정하는 과정에서 또 하나 막힌 것이 있는데, list를 초기화하려면 length가 필요한데 이를 무엇으로 지정해줄 것인가이다.
문제를 보면 위치 N과 K가 주어졌지만 스타트링크 문제처럼 이동할 수 있는 층수가 정해져있진 않다.

코드를 보면 알겠지만 10 ** 5를 visited 배열의 길이로 지정해주었다. 이 값은 N과 K의 최댓값이다. 남들은 당연하다고 생각할 수도 있지만 이런 방식을 처음 접한 나에겐 정말 기발한 생각이다.

처음엔 문제에 대한 접근법, 코드 모든 게 막막했지만 점점 정답근처까지는 가고 있는 것 같다. 코딩테스트 혹은 알고리즘은 결국 양치기라는 말이 있는데 하다보니 어느정도 납득이 된다. 꾸준히 해서 백준 골드 찍어보자!