[백준/Python] 숨바꼭질 1, 3 정리 (feat. 0-1 BFS, 다익스트라)

1697 - 숨바꼭질

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

1697번: 숨바꼭질

 

틀린 풀이

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

n, k = map(int, input().rstrip().split())
visited = [0] * 100001

def bfs():
	global board
	global visited
	
	q = deque([n])
	visited[n] = 0

	while q:
		x = q.popleft()

		for nx in [x-1, x+1, 2*x]:
			if 0<=nx<=100_000 and not visited[nx]:
				q.append(nx)
				visited[nx] = visited[x] + 1

bfs()
print(visited[k])

 

맞는 풀이

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

n, k = map(int, input().rstrip().split())
visited = [0] * 100001

def bfs():
	global board
	global visited
	
	q = deque([n])
	visited[n] = 0

	while q:
		x = q.popleft()

		if x == k:
			print(visited[k])
			break

		for nx in [x-1, x+1, 2*x]:
			if 0<=nx<=100_000 and not visited[nx]:
				q.append(nx)
				visited[nx] = visited[x] + 1

bfs()

 

두 풀이의 차이는 중간에 동생(k)에 도달했을 때 멈추느냐, 아니면 끝까지 탐색하고 후에 멈추느냐 인데 왜 서로 다른 결과가 나오는건지, 이 문제에서는 왜 중간에 멈춰야 하는건지 궁금해졌다.

질문게시판을 찾아보니, 처음부터 수빈이의 위치와 동생의 위치가 같아지는 지점이 존재할 수 있는데 (둘다 범위가 0부터 10만까지임), 이부분에서 서로 다른 예시가 나온다.

 

예를들어 입력이 6 6이라면, 틀린 풀이가 2, 맞는 풀이가 0이 나온다.

0초가 그냥 가장 빠른 정답인게 당연한데 이 조건을 주지 않으면 돌아가게 되므로 탐색하면서 걸리는 시간을 세게된다.

 

따라서 동생과 수빈이의 범위를 고려하여 중간에 뽑은 후보가 조건을 만족할 때 바로 출력 후 break를 해주어야한다.

 

13549 - 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

위 문제와 아래 문제 지문의 차이는, 순간 이동을 하는 경우에 1초/0초 후에 2*x 위치로 이동한다는 점에서 이동하는 경로의 가중치가 서로 다르다는 점이다.

BFS는 모든 간선 간 가중치가 같아야만 적용 가능하지만, 가중치가 0과 1로 구성되어있는 경우에는 0-1 BFS(사실 이 알고리즘도 다익스트라라고 볼 수 있지만 시간복잡도에서 차이), 그것이 아니고 가중치가 다르 값으로 구성되어있다면 다익스트라로 접근해야한다.

 

* 0-1 BFS란?

기존 BFS와 동일하나, 큐에 어떤 노드를 넣을지에 대한 순서가 다름. 가중치가 더 낮은 (0)의 값을 가지는 노드부터 큐의 가장 앞단에 삽입하여 먼저 가중치가 낮은 노드부터 접근할 수 있도록 하는 알고리즘이다.

 

시간 초과 풀이

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

n, k = map(int, input().rstrip().split())
visited = [0] * 100001

def bfs():
	global visited
	
	q = deque([n])
	visited[n] = 0

	while q:
		x = q.popleft()

		if x == k:
			print(visited[k])
			break

		if 0<=2*x<=100_000 and not visited[2*x]:
			q.appendleft(2*x)
			visited[2*x] = visited[x]

		for nx in [x-1, x+1]:
			if 0<=nx<=100_000 and not visited[nx]:
				q.append(nx)
				visited[nx] = visited[x] + 1

bfs()

 

7% 언저리에서 시간초과가 났는데, 그 이유는 2*x로 이동할 때 0초가 소요되는데 방문하지 않았다는 표시인 visited[x] == 0 과 0초가 걸린것과 구분이 되지 않으니, 탐색의 범위가 줄어들지 않음이라고 짐작해서, 로직을 수정했다.

 

맞는 풀이 (0-1 BFS)

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

n, k = map(int, input().rstrip().split())
visited = [False] * 100001

def bfs():
	global visited
	
	q = deque([(n, 0)])

	while q:
		x, dist = q.popleft()

		if x == k:
			print(dist)
			break

		if 0<=2*x<=100_000 and not visited[2*x]:
			q.appendleft((2*x, dist))
			visited[2*x] = True

		for nx in [x-1, x+1]:
			if 0<=nx<=100_000 and not visited[nx]:
				q.append((nx, dist+1))
				visited[nx] = True

bfs()

 

또한, 0-1 BFS도 따지고보면 가중치가 서로 다를 때의 최단 거리를 구하는 알고리즘인 다익스트라 중 하나이므로, 다익스트라로도 풀이해보았다.

 

다익스트라

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

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

# 2) 다익스트라
INF = int(1e9)
distance = [INF] * 100001
def dijkstra(start):
	q = []
	heapq.heappush(q, (0, start))
	distance[start] = 0

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

		for i in [(1, now+1), (1, now-1), (0, now*2)]:
			if 0<=i[1]<=100_000:
				cost = dist + i[0]
				if cost < distance[i[1]]:
					distance[i[1]] = cost
					heapq.heappush(q, (cost, i[1]))

dijkstra(n)
print(distance[k])