13549

날짜 : 2023. 03. 16

사용 언어 : python

 

문제

 

 

코드

from collections import deque
import sys

n, k = map(int, sys.stdin.readline().split())  # 시작점, 도착점
visited = [False] * 100001
visited[n] = True
move = [-1, 1]
res = []


def dfs(start, end, sec):  # 시작점, 도착점, 소요시간
    q = deque()
    q.append([start, sec])
    while q:
        now, t = q.popleft()
        #print(now, t)
        tele = now * 2  # 순간이동
        if now == end:
            res.append(t)
            return
        if tele in range(100001) and not visited[tele]:  # 범위에 있고 방문 x
            visited[tele] = True  # 방문처리
            q.append([tele, t])
        for i in range(2):
            next = now + move[i]  # 이동
            if next in range(100001) and not visited[next]:  # 범위에 있고 방문 안함
                visited[next] = True  # 방문처리
                q.append([next, t + 1])  # 이동
    return


dfs(n, k, 0)
print(min(res))

 

 

풀이

- 총 노드의 개수가 10만개이기 때문에 크기가 100001인 배열을 생성한다

- 시작점과 도착점을 입력받은 후 dfs를 실행한다

- 순간이동(tele)을 하는 경우 이동시간이 0인 특성상 가중치를 더하지 않고 처리한다

- 그 다음 일반 이동(+1, -1)을 하는 경우에는 1초가 소요되기 때문에 1을 가산하여 큐에 삽입한다

- 서로 가중치가 다르기 때문에 순간이동(가중치가 없음) -> 작은 수로 이동 -> 큰 수로 이동하는 순서로 판별, 큐에 삽입한다.

 

 

알게된 점

- 방법은 맞았지만 가중치가 다르기 때문에 (노드 - 1)을 (노드 + 1) 보다 우선적으로 판별해야 한다는 것을 모르고 +1부터 넣었다.

- 원래는 다익스트라로 푸는게 이상적인 풀이라고 한다.

 

참고 사이트

-