[Python] 1697번 숨바꼭질

✏️ 문제

 

문제 파악

동생을 찾는 "가장 빠른" 시간을 출력해야 하므로 BFS를 사용해야 한다.

for 반복문을 이렇게도 사용하는 지 몰랐는데 다음과 같이 for 문이 주어지면 ( ) 안의 인자들은 탐색하려는 다음 가능한 위치들을 말한다.

for a in (a - 1, a + 1, a + 2):
	...

 

위와 같은 경우 

1. 첫 번째 반복에서 a 에 a - 1 이 할당되어 반복문이 진행된다. 예를 들어 a 가 5라면 이때 a 는 4가 된다.
2. 두 번째 반복에서 a 에 a + 1 이 할당되어 반복문이 진행된다. 예를 들어 a 가 5라면 이때 a 는 6가 된다.
3. 세 번째 반복에서 a 에 a + 2 이 할당되어 반복문이 진행된다. 예를 들어 a 가 5라면 이때 a 는 7가 된다.

이 점을 활용하면 쉽게 문제를 풀 수 있다.

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

 

코드

from collections import deque

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

def bfs(v):
  q = deque([v])

  while q:
    v = q.popleft()

    if v == k:
      return graph[v]

    for next_v in (v-1, v+1, 2*v):
      if 0 <= next_v < 100001 and not graph[next_v]:
        graph[next_v] = graph[v] + 1
        q.append(next_v)

print(bfs(n))

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS