[BFS] 1697번 숨바꼭질

1. 문제

---

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

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

 

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

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

 

2. 풀이 사고 과정 

---

1. 방문한 위치를 또 방문하게 될 경우, 그 다음 방문 위치는 동일하기 때문에 경우의 수가 미친듯이 늘어남

2. 그러면 방문한 곳은 방문했다고 표시하고 방문하지 않아야 함 

--> 이것이 BFS의 기본 

3. 데크를 사용해서 수행시간을 줄이고 편하게 앞에서부터 순차적으로 pop하자 (popleft)

 

3. 파이썬 소스코드 

---

1. visited 체크를 앞부분에 하는 코드

: 이후 방문할 위치가 visited 일 때에도 현재 위치는 visited가 아니므로 조건에 걸리지 않아서 append를 함

그리고 다음 루프에서 visited!=True 조건에 걸림

from collections import deque
def bfs(N):
    count = 0
    q = deque([[N, count]])

    while q:
        v = q.popleft()
        position = v[0]
        count = v[1]
        if visited[position] != True:
            visited[position] = True
            if position == K:
                return count

            count += 1
            if position * 2 <= 100000:
                q.append([position * 2, count])
            if position + 1 <= 100000:
                q.append([position + 1, count])
            if position - 1 >= 0:
                q.append([position - 1, count])
    return count
    

N, K = map(int, input("").split(" "))
visited = [False for _ in range(100001)]
print(bfs(N))

2. visited 체크를 뒤에 하는 코드 

: 미리 다음 방문 위치가 visited 인지 체크를 하고 이미 방문했다면 append 안함 

그러므로 수행시간이 더 빠름 

from collections import deque
def bfs(N):
    count = 0
    q = deque([[N, count]])

    while q:
        v = q.popleft()
        position = v[0]
        count = v[1]
        if position == K:
            return count

        if (position * 2 <= 100000) and (not visited[position*2]):
            q.append([position * 2, count+1])
            visited[position*2] = True
        if (position + 1 <= 100000) and (not visited[position+1]):
            q.append([position + 1, count+1])
            visited[position+1] = True
        if (position - 1 >= 0) and (not visited[position-1]):
            q.append([position - 1, count+1])
            visited[position -1] = True
    return count
    

N, K = map(int, input("").split(" "))
visited = [False for _ in range(100001)]
print(bfs(N))

+ 근데 그럼 첫번째 방문 위치는 visited로 표시가 안되나 ? 

 

4. 수행시간 비교 

---

위에 있는 코드가 2번째 코드인데 수행시간이 1번째 코드보다 더 빠른 것을 볼 수 있다.