[백준] 1697 숨바꼭질

숨바꼭질

• 티어 : Silver 1
• 시간 제한 : 2 초
• 메모리 제한 : 128 MB
• 알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입출력

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

---

Algorithm

1. BFS - 최단거리 이용 
2. while문 돌면서 각 노드마다의 최단거리 탐색
3. 동생이 있는 곳에 도착하면 return 

Run Time Error - Index Error
➝ visited 리스트의 값이 0보다 큰지 비교하는 if문에 i의 범위를 지정


시간 초과 - 이걸로 고생 엄청 많이 함 ㅠㅠ
: 100000 100000, 1 1과 같은 거리가 0인 Test Case를 해결하지 못하는 문제
➝ for문 내에서 queue안에 K가 있으면 RETURN 하는 방식으로 구현했더니 리스트가 너무 길어져서 절대 못찾음 ㅠ
➝ 차라리 FOR문을 좀 더 돌더라도 FOR문 밖에서 X가 K가 되면 RETURN하도록 구현 !

Code

from collections import deque
def bfs(start):
    
    # 현재 위치에 이미 방문한 적 있으면 무시
    if visited[start] > 0:
        return False
    
    # 현재 위치 방문 기록
    visited[start] = 1
    
    queue = deque([start])
    while queue:
        
        x = queue.popleft()

        # 위치 이동
        for i in graph[x]:
            # 이미 방문한 곳이라면 무시

            if i < 0 or i > MAX-1 or visited[i]>0:
                continue

            queue.append(i)
            visited[i] = visited[x] + 1
            
        if x == K:
            return visited[K] - 1
    return True

# 입력
N, K = map(int, input().split())
MAX = 100001
# 그래프 생성
graph = [[] for _ in range(MAX)]
for i in range(MAX):
    graph[i] = [i-1, i+1, i*2]
visited = [0] * (MAX)

print(bfs(N))

메모리: 53984 KB
시간: 216 ms