1697번: 숨바꼭질

1697번: 숨바꼭질

---

최단 경로 -> BFS

BFS를 사용해서 풀면 되는 문제다.

 

---

풀이 코드

# 1697번: 숨바꼭질
from collections import deque

n,k = map(int, input().split())
visited = [0] * 100002 # 방문 여부 + 해당 인덱스에 방문하기 까지 걸린 시간을 저장하기 위한 리스트

def bfs(n, k):
    if n == k: # 동생과 위치가 같다면 그대로 0 리턴
        return 0
    queue = deque([n]) # 시작점을 큐에 넣는다.
    
    while queue:
        now = queue.popleft()
        
        if now + 1 < 100001 and visited[now + 1] == 0:
            queue.append(now + 1)
            visited[now+1] = visited[now] + 1
        if now > 0 and now * 2 < 100001 and visited[now * 2] == 0:
            queue.append(now * 2)
            visited[now * 2] = visited[now] + 1  
 
        if now - 1 >= 0 and visited[now - 1] == 0:
            queue.append(now - 1)
            visited[now-1] = visited[now] + 1

        # k가 0이 아니라면 해당 시간이 가장 빠른 시간
        if visited[k] != 0:
            return visited[k]



print(bfs(n, k))

 

문제 조건에서 점 0에도 방문할 수 있다고 했는데, 이걸 빼먹어서 해결에 오래 걸렸다.

문제를 자세하게 읽는 습관을 들여야겠다.

 

 

개선된 코드

# 1697번: 숨바꼭질
from collections import deque

n,k = map(int, input().split())
visited = [0] * 100001 # 방문 여부 + 해당 인덱스에 방문하기 까지 걸린 시간을 저장하기 위한 리스트

def bfs(n, k):
    if n == k: # 동생과 위치가 같다면 그대로 0 리턴
        return 0
    queue = deque([n]) # 시작점을 큐에 넣는다.
    
    while queue:
        now = queue.popleft()
        
        for next in ([now - 1, now + 1, now * 2]):
            if next >= 0 and next <= 100000 and visited[next] == 0:
                visited[next] = visited[now] + 1
                queue.append(next)

        # k가 0이 아니라면 해당 시간이 가장 빠른 시간
        if visited[k] != 0:
            return visited[k]



print(bfs(n, k))