13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
이번 문제는 bfs와 다익스트라 두 가지 방법으로 풀이할 수 있다.
전에 bfs 문제를 풀 때 다루었던 문제랑 똑같은게 아닌가? 했는데
이 문제에서는 가중치를 고려해야한다.
그래서 전에 풀었던 bfs 방식에서 가중치를 고려하여 살짝 변형하여 풀고
최근에 학습한 다익스트라로도 코드를 짜 보았다.
[BFS]
import sys
from collections import deque
# 13549 bfs
input = sys.stdin.readline
n,k = map(int, input().split())
lst=[0]*100001
def bfs(n, k):
q = deque()
q.append(n)
lst[n] = 1
while q:
start = q.popleft()
if start == k:
return lst[k]
for i in (start*2,start-1,start+1):
if i >=0 and i <= 100000 and lst[i] == 0:
if i == start*2:
lst[i] = lst[start]
q.appendleft(i)
else:
lst[i] = lst[start]+1
q.append(i)
print(bfs(n,k)-1)
가중치를 고려해야 하므로 순간이동을 할 때(가중치가 0일 때)를 항상 먼저 탐색해야 한다.
따라서 appendleft()를 사용하여 덱의 가장 앞에 넣어주어 우선 탐색을 하도록 하였다.
처음 최대값 고려를 하지못해 index에러가 났고
그 다음에는 처음 시작 값 n의 거리값을 바꿔주지않아 시간 초과가 걸렸다.
두 가지를 해결하니 무사히 통과했다.
[dijkstra]
import sys
import heapq
# 13549 dijkstra
input = sys.stdin.readline
INF = int(1e9)
def dijkstra(n,k):
dist=[INF]*100001
q = []
dist[n] = 0
heapq.heappush(q, (0,n))
while q:
weight, curr = heapq.heappop(q)
if curr == k:
return dist[k]
if dist[curr] < weight:
continue
for cost, next in [(0, curr*2), (1, curr+1), (1, curr-1)]:
next_w = weight + cost
if 0<= next <= 100000 and next_w < dist[next]:
dist[next] = next_w
heapq.heappush(q, (next_w, next))
n,k = map(int, input().split())
print(dijkstra(n,k))
bfs와 비슷한데 deque 대신 heapq를 사용하여 가중치가 가장 작은 것 부터 탐색한다.
728x90
'자료구조 & 알고리즘 & cs > CodingTest' 카테고리의 다른 글
[java/python] 프로그래머스 Lv2. - JadenCase 문자열 만들기 (0) | 2023.05.17 |
---|---|
[java/python] 프로그래머스 Lv2. - 하노이 탑 (0) | 2023.05.16 |
[python/java] 프로그래머스 Lv2. - 최솟값 만들기 (0) | 2023.05.05 |
[python] 프로그래머스 Lv2. - 줄 서는 방법 (0) | 2023.05.05 |
[java/python] 프로그래머스 Lv2. - 숫자의 표현 (0) | 2023.05.04 |