백준 12851: 숨바꼭질 2 (BFS 활용)

문제

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

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

 

접근

N에서 시작하여 K에 도달하는 경우 중 최단 이동거리를 만족하는 경우를 체크하면 되는 문제이다.

BFS를 이용하면 K에 도달하는 경우를 최초로 발견한 시점이 곧 최단 이동거리를 달성한 시점이므로 BFS를 활용해 코드 초안을 잡아보자.

 

from collections import deque

def bfs(n, k, visited):
    q = deque()
    visited[n] = 1 # 방문기록 체크
    q.append([n, 0, visited]) # 현재 수빈이의 위치와 이동 횟수, 그리고 방문 기록 넣음
    moved_ans = 1000000
    return_ans = 0
    move_list = [1, -1, 2]
    all_length = len(visited)

    while q:
        now, moved, now_visited = q.popleft()
        if now == k:
            if moved <= moved_ans:
                moved_ans = moved
                return_ans += 1
            else:
                return moved_ans, return_ans
        
        for i in range(3): # 현재 위치에서 이동 가능한 방법은 총 3가지
            if move_list[i] == 1 and 0 <= now + 1 < all_length and visited[now + 1] == 0:
                n_now = now + 1
                now_visited_1 = now_visited[:]
                now_visited_1[n_now] = 1
                q.append([n_now, moved + 1, now_visited_1])

            elif move_list[i] == -1 and 0 <= now - 1 < all_length and visited[now - 1] == 0:
                n_now = now - 1
                now_visited_1 = now_visited[:]
                now_visited_1[n_now] = 1
                q.append([n_now, moved + 1, now_visited_1])

            elif move_list[i] == 2 and 0 <= now * 2 < all_length and visited[now * 2] == 0:
                n_now = now * 2
                now_visited_1 = now_visited[:]
                now_visited_1[n_now] = 1
                q.append([n_now, moved + 1, now_visited_1])

n, k = map(int, input().split()) # n: 수빈이 위치, k: 동생 위치

visited = [0] * (2 * max(n, k) + 1)
answer_moved, answer_type = bfs(n, k, visited)


print(answer_moved)
print(answer_type)

 

(위의 코드에서 move_list[i] 의 값에 따라 elif문을 새로이 적어주는 것이 아닌 move_list를 [now + 1, now - 1, now * 2]로 두고 진행하는 편이 훨씬 나았을 것 같다.)

 

작성한 코드를 제출해보니 메모리 초과가 발생하였다. 그 이유는 '모든 루트에 대해 visited 리스트를 새로 만들어 주기 때문' 이라고 생각했다. 이를 해결하기 위해 하나의 visited 리스트를 가지고 BFS 완전탐색을 수행하기 위한 방법을 고안해보았다.

 

visited 리스트를 만들고 visited[i]에 i에 도달하기 위해 이동한 횟수를 집어넣는다.

주의할 점은 이동 횟수를 집어넣기 전에 기존에 들어가있는 값을 체크하는 것이다.

만약 기존의 값이 0이라면 아직 방문하기 전 이므로 괜찮다. 이동 횟수값을 넣어도 된다.

기존의 값이 0이 아니라면 넣고자 하는 값과 들어가있는 값을 비교하고, 넣고자 하는 값이 들어가있는 값 이하일 경우 넣어주도록 하자.

이동횟수가 최소가 되는 경우의 수를 계산하고 싶은 것이니 말이다.

 

위의 논리를 코드에 적용하면 다음과 같다.

from collections import deque

def bfs(n, k, visited):
    q = deque()
    visited[n] = 1 # 방문기록 체크
    q.append([n, 0]) # 현재 수빈이의 위치와 이동 횟수, 그리고 방문 기록 넣음
    moved_ans = 1000000
    return_ans = 0

    while q:
        now, moved = q.popleft()
        if now == k:
            if moved <= moved_ans:
                moved_ans = moved
                return_ans += 1
            else:
                break
        
        for i in [now + 1, now - 1, now * 2]:
            if 0 <= i < len(visited) and (visited[i] == 0 or visited[i] >= moved + 1):
                visited[i] = moved + 1
                q.append([i, moved + 1])

    return moved_ans, return_ans


n, k = map(int, input().split()) # n: 수빈이 위치, k: 동생 위치
visited = [0] * (2 * max(n, k) + 1)
moved, type = bfs(n, k, visited)

print(moved)
print(type)