1697. 숨바꼭질

https://www.acmicpc.net/problem/1697

이해

• N에서 K까지 가는 길을 완전탐색을 통해 해결
• 다익스트라를 통해 해결도 가능할 것 같아 풀어봄
• 방문 확인용 배열에 최솟값을 저장해 가지치기를 할 수 있음
• N == K 인 경우, 조건문을 통해 배열에 넣고, 빼는 시간을 줄임

구현

1. 방문 확인용 배열 및 후보 과정을 담을 배열 생성
2. 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행
3. 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가

코드

• 너비우선탐색

# 35388KB	140ms
import sys
from collections import deque

N, K = map(int, sys.stdin.readline().strip().split())

# 기본 세팅
queue = deque([N])
# 최댓값으로 최소 저장 변수설정
min_cnt = abs(K-N)
# 방문 체크용 배열
visited = [0] * (10**5+1)
# 만약 같은 곳에 있으면 탐색할 이유 없음
if N == K:
    print(0)
else:
    while queue:
    	# 현재 위치
        now = queue.popleft()
        if now == K:
        	# 만약 만났으면 최소 설정
            min_cnt = min(min_cnt, visited[now])
        elif visited[now] > min_cnt:
        	# 이미 큰 경우는 가지치기
            pass
        else:
        	# 범위 내에 있으면 방문 확인 후 queue에 넣어 다음 후보로 저장
            if now -1 >= 0 and not visited[now-1]:
                queue.append(now-1)
                visited[now-1] = visited[now] + 1
            if now + 1 <= 100000 and not visited[now+1]:
                queue.append(now+1)
                visited[now+1] = visited[now] + 1
            if (now <<1) <= 100000 and not visited[now<<1]:
                queue.append(now<<1)
                visited[now<<1] = visited[now] + 1
    print(min_cnt)

• 다익스트라

# 36020KB	196ms
import sys, heapq

N, K = map(int, sys.stdin.readline().strip().split())

if N == K:
    print(0)
else:
    # dijkstra
    queue = []
    heapq.heappush(queue, (0, N))
    # 방문 확인
    visited = [0] * (10**5+1)             
    visited[N] = 1
    while queue:
        cnt, now = heapq.heappop(queue)
        if now == K:
            # 맨 처음이 최단 경로
            print(cnt)
            break
        else:
            # 범위 확인 과 방문 확인 후 후보군 저장
            if now -1 >= 0 and not visited[now-1]:
                heapq.heappush(queue, (cnt+1, now-1))
                visited[now-1] = 1
            if now + 1 <= 100000 and not visited[now+1]:
                heapq.heappush(queue, (cnt+1, now+1))
                visited[now+1] = 1
            if (now <<1) <= 100000 and not visited[now<<1]:
                heapq.heappush(queue, (cnt+1, now<<1))
                visited[now<<1] = 1

느낀점

• 다익스트라와 가지치기를 통한 너비우선탐색(백트래킹)의 시간과 메모리를 비교 했을 때, 당연히 다익스트라가 빠를 줄 알았는데, N의 범위 때문인지 다익스트라가 더 많이 나와 우선순위 큐의 정렬 과정이 생각보다 시간이 많이 드는 것을 몸소 느낄 수 있었다.
• 후보 과정을 배열에 담는 코드에서 반복문을 통해 더욱 간단히 넣는 방법이 있었다.(아래 코드 참조)

for next in [now-1, now+1, now*2]:
	if 0 <= next < limit and not visited[next]:
        heapq.heappush(que, (cost+1, next))
        visited[next] = 1