백준 13549 - 숨바꼭질 3 (Python3)

코드

BFS 활용

from collections import deque

n, k = map(int, input().split())
max_range = 100001
visited = [0 for _ in range(max_range)]

def bfs(n):
    q = deque()
    q.append(n)
    
    while q:
        x = q.popleft()
        
        if x == k:
            return
        
        for nx in (x-1, x+1, x*2):
            if nx < 0 or nx >= max_range:
                continue

            if visited[nx] == 0:

                if nx == x*2:
                    visited[nx] = visited[x]
                    q.appendleft(nx)
                else:
                    visited[nx] = visited[x] + 1
                    q.append(nx)
                    
bfs(n)

print(visited[k])

다익스트라 활용

import heapq

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

INF = int(1e9)
max_range = 100001

dist_table = [INF for _ in range(max_range)]

def dijkstra(start):
    q = []
    
    heapq.heappush(q, (0, start))
    dist_table[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
            
        for nx in (now-1, now+1, now*2):
            if nx < 0 or nx >= max_range:
                continue
            
            if dist_table[nx] == INF:
                if nx == now*2:
                    dist_table[nx] = dist
                    heapq.heappush(q, (dist, nx))
                else:
                    dist_table[nx] = dist + 1
                    heapq.heappush(q, (dist+1, nx))
    print(dist_table[k])
    
                
dijkstra(n)

다익스트라 활용 - Generator 사용

import heapq
INF = int(1e9)

n, k = map(int, input().split())
max_range = 100001
dist_table = [INF for _ in range(max_range)]
    
# 인접 노드들을 iterable한 값으로 리턴하기 위한 Generator 함수
def move(x):
    yield (x-1, 1)
    yield (x+1, 1)
    yield (2*x, 0)
    
# 다익스트라 알고리즘
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist_table[start] = 0
    
    while q:
        dist, now = heapq.heappop(q)
        
        if dist > dist_table[now]:
            continue
        
        # 0부터 100000까지의 모든 노드들은, 조건 범위 안에서
        # 자신의 -1, +1, *2의 인접 노드를 가짐
        # 그래서 제너레이터를 통해 직접 인접 노드를 구하여 순회하면 됨
        for v, w in move(now):
            cost = dist + w
            
            # 인접 노드로 구한 값이 조건 범위 안에 있어야 함
            if 0 <= v <= 100000 and cost < dist_table[v]:
                dist_table[v] = cost
                heapq.heappush(q, (cost, v))
    
    return dist_table[k]

print(dijkstra(n))

문제 해설

[][숨바꼭질]숨바꼭질의 변형 문제.

움직일 때마다 소요되는 시간이 모두 같았던 기존의 문제와는 달리, 순간 이동을 할 때는 소요 시간이 0이 되는 부분이 다르다. 즉, 노드를 이동하는 경우마다 가중치가 다른 경우이므로 BFS뿐만 아니라 다익스트라 알고리즘을 사용해도 풀 수 있는 문제.

문제 풀이 자체는 크게 어렵지 않았다.

---

1. BFS의 경우
   • visited 테이블의 값이 0인 경우, 순간 이동과 앞 뒤로 움직이는 경우를 나누어서 큐에 넘겨줌
2. 다익스트라의 경우
   • 최단 거리 테이블이 초기화된 후 갱신되지 않은 경우, 위와 동일하게 최소힙에 넘겨줌

---

풀이 방법에 대한 참고를 하던 중, 파이썬의 Generator를 활용하여 푸는 방식도 알게 되었다. 이 방식이 코드가 가장 간결하고 문제가 복잡해질 경우 좀 더 메모리 차원에서 이득을 볼 수 있는 것 같아 Generator에 대한 별도의 공부를 실시하고 문제 풀이를 습득하였다.

Generator 참고 블로그

---

• 연관된 문제 링크

  • 숨바꼭질

  • 숨바꼭질 2

  • 숨바꼭질 4

---