[BOJ/백준] 1697번 숨바꼭질 | BFS | 파이썬

문제 

풀이

from collections import deque

def bfs(start, end):
    queue = deque()
    queue.append(start)
    while queue:
        x = queue.popleft()
        if x == end:
            return visited[x]
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= max_input and visited[nx] == 0: #또는 not visited[nx]
                visited[nx] = visited[x] + 1   
                queue.append(nx)
n, k = map(int, input().split())
max_input = 100000
visited = [0] * (max_input + 1)
print(bfs(n, k))

 

BFS로 1차원 배열을 푸는 문제

 

문제에서 위치 값 범위를 벗어나지 않도록 max_input 값을 정의했다.

방문 여부를 확인하기 위해 visited 변수를 만들었다. 

 

함수 bfs를 만들어 걸리는 최소 시간을 구했다.

• deque()을 사용해서 queue 변수를 정의하고 시작 값을 추가했다.
• queue에 값이 없을 때 까지 while문을 실행한다.
• x 변수에 popleft()로 꺼낸 값을 넣는다.
• 만약 x값이 end값, 즉 동생의 위치와 같으면 visited[x] 값을 반환한다.
• 그렇지 않으면 for문으로 걷거나 순간이동(x-1, x+1, x*2)을 한다.
• nx가 위치 값 범위를 벗어나지 않고 visited[nx]가 0인 경우(방문하지 않은 경우) queue에 추가했다.
• 걷거나 순간이동하는 것은 1초마다 일어난다. 방문 여부를 시간처럼 쓰기 위해 visited[nx]값을 visited[x] + 1로 바꿨다. 

 

x-1, x+1, x*2를 어떻게 깔끔하게 반복할 수 있을 까 고민했는데 for nx in (x-1, x+1, x*2)처럼 쓰는 방법이 있었다👍

 

---

드디어 실버5🤍🤍🤍 프로필이랑 너무 잘 어울리는구만,,,

1697번: 숨바꼭질