BOJ [숨바꼭질 3], bfs개념 확장

문제

문제 보기

0 이상 100,000 이하의 수 A,B가 주어진다.

A, B는 수직선위에 있다.

A는 +1 or -1 or *2로 이동 가능하다.

+1, -1 은 1초를 소비하고 *2는 0초를 소비한다.

A에서 B로가는 최소시간을 구하라는 문제이다.

얻어간 개념

뭔가 10만이라 dijkstra로 풀면 시간 초과가 날것 같아 bfs로 접근했다.

결론으로는 dijkstra가 맞는 방법이었다.

0초, 1초가 걸려 weight가 다르지만 어차피 step순서로 진행되므로

처음 B에 도달하는 순간이 가장 최솟값일 것이라 생각했다.

하지만 아니었다.

종회형한테 물어보니 step 단위로 접근하는 bfs의 특성을 적용하기 위해서는

cost가 같아지는 모든 접근을 한 step으로 봐야된다 한다.

이 문제로 치면

x+-1

2x+-1

4x+-1

16x+-1

...

가 모두 한 step인 것이다.

10만 제한이 있으므로 10만을 넘기전까지 while문을 돌리면 bfs로 풀 수

있다고 한다.

5.25 추가

dijkstra로 풀면 모든 노드까지의 최소거리를 구할 수 있지만 그만큼 많은 시간이 쓰인다. bfs를 쓸 수만 있으면 모든 거리를 조사하지 않고 문제를 풀 수 있을 것이다. 현아의 풀이를 보고 새로운 개념을 얻었다. bfs에 heapq를 사용하는 것이다. cost를 기준으로 heapq를 사용하면 *2연산이 cost가 0이어서 제일 앞으로 계속 옴으로 한 step 단위로 처리가 가능해진다. 하지만 n의 범위가 10만 이하이므로 가능한 풀이이기도 하다. 코드는 밑에 첨부한다.

코드

다잌스트라 풀이

import heapq

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

distance = [1e9] * 100001

def dijkstra(n,distance):
	distance[n] = 0
	q= []
	heapq.heappush(q,(n,0))

	while q:
		now, cost = heapq.heappop(q)

		if distance[now] < cost:
			continue

		if now*2 < 100001 and distance[now*2] >cost:
			distance[now*2] = cost
			heapq.heappush(q,(now*2,cost))

		if now-1 >= 0 and distance[now-1] >cost+1:
			distance[now-1] = cost+1
			heapq.heappush(q,(now-1,cost+1))

		if now+1 < 100001 and distance[now+1]>cost+1:
			distance[now+1] = cost+1
			heapq.heappush(q,(now+1,cost+1))
		
dijkstra(n,distance)


print(distance[m])

BFS 풀이

import heapq
INF = float('inf')
def bfs(start):
    global answer
    h = []
    heapq.heappush(h, (0, start))
    visited = [False]*100001
    visited[start] = True

    while h:
        dis, now = heapq.heappop(h)
        if now == K:
            return dis
        if 0<=now*2<=100000 and not visited[now*2]:
            visited[now*2] = True
            heapq.heappush(h, (dis, now*2))


        if 0<=now-1<=100000 and not visited[now-1]:
            visited[now-1] = True
            heapq.heappush(h, (dis+1, now-1))

        if 0<=now+1<=100000 and not visited[now+1]:
            visited[now+1] = True
            heapq.heappush(h, (dis+1, now+1))


N, K = map(int, input().split())
# answer = float('inf')
# bfs(N)
print(bfs(N))

now2부터 보는게 중요하다. now+1 == now2이 같은 경우가 있다. now+1이 먼저들어가면 visited 가 true가 되어 now*2의 cost가 더 작음에도 들어가지 못한다.