1 minute read

문제

접근 방법

문제 상황이 어려워보이지만 일단은 두 점 사이의 최단 거리를 구하는 문제이기 때문에 BFS나 dijkstra를 사용하는 것을 염두하였다.

하지만 틀렸다.. ㅋㅋ Dijkstra를 사용하면 바로 풀릴 거라고 생각하지만 BFS를 사용해서 풀어봤는데 생각대로 안 됐다.

우선 dijkstra 풀이는 heapq 때문에 간단하다.

Dijkstra 풀이

import sys
import heapq

inf = int(1e9)
input = sys.stdin.readline

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

def get_moves(node):
    return [(node-1,1), (node+1,1), (node*2,0)]
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0,start))
    distance = [inf for _ in range(200001)]
    distance[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if(distance[node] < dist):
            continue
        moves = get_moves(node)
        for move,cost in moves:
            if(move<0 or move>200000):
                continue
            new_dist = dist+cost
            if(new_dist< distance[move]):
                distance[move] = new_dist
                heapq.heappush(q, (new_dist, move))
    return distance

result = dijkstra(n)
print(result[k])

하지만 BFS는 queue를 사용하기 때문에 다음 조사할 노드의 우선순위를 조절해줘야 한다. queue에서 pop이 아니라 popleft를 하는 이유는 제일 가까운 노드에 대해서 먼저 조사하기 위해서다. 따라서, 매 이동마다 제일 가까운 노드, 즉 현재에서 다음에 우선순위가 제일 높아야 하는 노드는 현재 위치에서 순간이동을 해서 이동한 노드이다.

내가 틀린 이유는 평소의 bfs처럼 moves = [(0,1), (0,-1) … ]처럼 모든 이동 방법을 동일하게 여겨서 그렇다. 평소의 문제들은 가중치가 다 1로 동일하기 때문에 동일하게 여겨도 상관없지만 가중치가 0과 1로 나뉠 때는 queue에 넣는 순서에 대해서 생각해야 한다.

BFS 풀이

import sys
from collections import deque
input = sys.stdin.readline

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

'''
가중치가 0,1만 존재하는 상황에서 최단 거리 구하기 -> 1/0 BFS가 dijkstra보다 빠름
'''

def bfs(start):
  q = deque()
  q.append(start)
  distance = [-1]*(100001)
  distance[start] = 0
  while q:
    loc = q.popleft()
    if loc == k:
      return distance[loc]
		# 순간이동으로 인해 특정 노드로 가는 최소거리가 줄어들 수 있으므로 이를 고려한다.
    if 0<= loc*2 <= 100000 and (distance[loc*2]==-1 or distance[loc*2] > distance[loc]):
      distance[loc*2] = distance[loc]
      # 무조건 제일 가까운 (순간이동) 노드를 넣을 때는 appendleft를 통해 항상 queue의 앞에 있도록 한다.
      q.appendleft(loc*2)

    if 0<= loc+1<= 100000 and distance[loc+1]==-1:
      distance[loc+1] = distance[loc]+1
      q.append(loc+1)
      
    if 0<=loc-1<= 100000 and distance[loc-1]==-1:
      distance[loc-1] = distance[loc]+1
      q.append(loc-1)

print(bfs(n))

배운 점

가중치가 다양할 때는 BFS의 queue에 넣는 순서를 생각하자.

You May Also Enjoy