[백준] 1697:숨바꼭질

BFS

  • 전형적인 bfs 문제이다
  1. cnt 를 셀 수 있는 배열을 하나 만든다.
  2. bfs 조건에 맞으면 1 증가 시킨다.
  3. 비교 할 것과 목표 값이 같으면 목표값의 배열 값을 출력한다.
    index 에러 났음 , pop한 값이 10만 보다 크면 continue
from collections import deque
n, k = map(int, input().split())
dx = [2, 1, -1]
come = [0 for _ in range(200001)]
visited = [False] * 200001
def bfs(x):
	queue = deque([x])
	visited[x] = True
	while queue:
		v = queue.popleft()
		if v == k:
			break
		if v > 100001:
			continue
		for i, h in enumerate(dx):
			if i == 0:
				nx = v * h
			else:
				nx = v + h
			if nx < 0 or nx > 200001:
				continue
			if visited[nx] == True:
				continue
			else:
				visited[nx] = True
				queue.append(nx)
				come[nx] = come[v] + 1
	return come[v]
print(bfs(n))

좋은 웹페이지 즐겨찾기