[BOJ] 숨박꼭질 3 in Python

문제풀러 가기!

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

처음에는 다익스트라로 접근했습니다. heapq를 사용하면 바로 풀 수 있을 것으로 생각했습니다. 결론적으로 말씀드리자면, 풀 수 있습니다. 근데 시간이 좀 많이 오래걸리네요. 도중에 더 좋은 풀이가 없을지 찾아보았습니다. python은 워낙 코테 풀이가 좋아서 deque로 풀 수 있는 방법이 있드라구요. 그래서 오늘은 제가 풀이한 코드와 많이 돌아다니는 풀이를 2개 모두 알아볼까 합니다.

참고로 어떤 풀이가 더 좋은가? 에 대해서는 독자들이 판단하는게 좋을거 같습니다. 전 솔직히 많이 돌아다니는 풀이가 더 좋은 것 같습니다. 이유는 문제에서 요구하는 부분을 잘 파악하고 짠 느낌이 들어요. 그렇기 때문에 더 효율적인 코드가 나온게 아닌가? 하는 느낌도 많았습니다.

일단 문제에서 요구하는 것은 수빈이가 동생이 있는 지점까지 갈 때 가장 짧은 거리가 몇인지를 구하는 문제였습니다.
각 점에서 이동할 수 있는 지점이 정해져있다는 것은 문제 풀이에 가장 큰 영향을 미치고 있습니다. 갈 수 있는 지점에 아에 정해져 있어서 그 부분만 보면 되거든요. 이런 부분은 약간 자료구조를 선형적으로 가져가도 된다는 의미로 생각할 수 있지 않을까요? 그래서 많이 돌아다니는 풀이는 코드 길이가 정말 짧아요. 그리고 엄청 효율적이죠.

많이 돌아다니는 풀이

from collections import deque

n, k = map(int,input().split())
node = [-1 for _ in range(100001)]
node[n] = 0
q = deque()
q.append(n)


while q:
    now = q.popleft()
    if now == k:
        print(node[now])
        break

    if 0 < 2*now < 100001 and node[2*now] == -1: # 1번, 가장 먼저 수행해야 가장 빠른 길을 찾을 수 있음.
        node[2*now] = node[now]
        q.appendleft(2*now)

    if 0 <= now + 1 < 100001 and node[now+1] == -1:
        node[now+1] = node[now] + 1
        q.append(now+1)

    if 0 <= now - 1 < 100001 and node[now-1] == -1:
        node[now-1] = node[now] + 1
        q.append(now-1)

1번 코드가 제일 중요합니다. 해당 코드에서 나타내는 것은 큐 자료구조에서도 우선순위를 가리겠다는 의미를 지니고 있거든요. 그래서 순간이동을 하는 가장 적은 비용을 수반하는 코드가 가장 먼저 실행될수 있도록 가장 먼저 q담도록 하고 있습니다. 그리고 또 저는 지금껏 사용하지 않은 method인 appendleft()를 사용했습니다. popleft()처럼 deque에서 사용할 수 있을 때 많이 사용해야겠습니다. 여튼 위 풀이의 가장 큰 장점은 비용이 0인 순간이동을 가장 먼저 실행하고 찾기 때문에 가장 비용이 적은 답을 빠르게 찾을 수 있다는 것입니다.

나의 풀이

from heapq import heappop, heappush

n, k = map(int, input().split())
node = [[] for _ in range(1000002)]

for i in range(100001): # 2번: 그래프 생성
    if i <= 50000:
        node[i].append((2*i, 0))
    node[i].append((i-1, 1))
    node[i].append((i+1, 1))


def dijkstra(s, e, node):
    INF = 100000
    dist = [INF for _ in range(1000002)]
    dist[s] = 0

    q = []
    heappush(q, (0, s))

    while q:
        distance, now = heappop(q)

        if dist[now] < distance:
            continue

        for nxt, dis in node[now]:
            cost = dis + distance

            if cost < dist[nxt]:
                dist[nxt] = cost
                heappush(q, (cost, nxt))
    return dist[e]

print(dijkstra(n, k, node))

제 풀이는 정말 가장 정형적인 풀이에요. graph를 구성하고 dijkstra 돌리기.. 맨 처음에 graph를 어떻게 구성해야 하나 생각했습니다. 그래서 2번과 같은 코드가 나온 것이죠. 그리고 그냥 다익스트라 돌렸습니다. 무지성이었죠... 그래서인지 풀이 결과를 비교하면 다음과 같아요... 약간 충격적입니다.

네.. 속도가 거의 4~5배 차이가 납니다. 문제의 제한시간이 2초였기 때문에, 둘 다 별 상관없는 풀이긴 하지만, 그래도 전 약간 충격이네요. 최근들어서 다시 알고리즘 풀이를 시작했는데, 정진해야겠다는 생각을 하게됩니다. 사실 요새 구현 문제를 많이 풀었습니다...ㅋㅋㅋ

다음에 또 올리겠습니다! 화이팅!