[백준 1697번] 숨바꼭질

원본 링크

https://www.acmicpc.net/problem/1697

문제

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

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

입력

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

출력

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

예제 입력

5 17

예제 출력

4

힌트

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

주 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색 (BFS)

나만의 풀이

맨 처음 보자마자 든 생각은 약간 우박수 문제를 변형한 느낌이 났다. (박수 박수 우박수)
다만 이 문제는 시작점도 다르고 좌표계 범위라는 제약 조건도 있었다.
따라서 무작정 loop를 도는 것보단 분기를 나눠서 탐색하는 방식이 적합하다 생각했다.
주 알고리즘 분류도 열어보니 Breadth First Search (일명 BFS)라고 되어있어서 바로 아!하고 생각했다.

본격적인 코드를 짜기에 앞서서 주어진 예제에 해당하는 BFS 과정을 그려나가보도록 하자.
먼저, BFS의 탐색과정을 다음의 도식을 토대로 이해해보자.

나의 경우는 다음의 순서대로 검색을 수행할 예정이다.
맨 처음 루트원소 5에서 출발해서 각각 x-1, x+1, 2x라는 원소를 생성해서 자식 노드로 만든다.
이후 '4 -> 6 -> 10' 순서대로 그 하단 노드를 생성하고 서치할 생각이다.
다만, 진짜로 트리를 만들 생각은 없기에, 다음에 방문해야 할 값과 현재까지 방문한 노드들의 정보를 저장하는 형태로 구현할 생각이다.

만일 상위 노드들 중에서 이미 방문한 값인 경우면 굳이 자식노드를 만들 필요가 없다.
왜냐고 물을 수 있는데 이유는 진짜 단순하다.
위 상황과 같이 5에서 시작했을 때, 5에 가만히 있는 경우랑 '5 -> 4 -> 5'로 가는 것 중 뭐가 이동 횟수가 더 적을까?
당연히 가만히 있는 경우다.
따라서 이전에 방문한 위치(값)가 나오면 그건 무시해주면 된다.

이는 바로 조상 노드 말고 다른 상위 레벨의 노드에게도 적용할 수 있다.
저기 빨간색 줄 쳐놓은 8이라는 값을 보면, 조상 노드에 8이라는 숫자가 없음에도 불구하고 확장하지 않았다.
그 이유는, 5에서 8까지 가기 위해선 '5 -> 10 -> 9 -> 8' 보다 '5 -> 4 -> 8'이 더 빠르기 때문이다.
따라서 조상이건 아니건 간에 상위 레벨에서 방문했던 친구들은 다 버려주면 된다.

이제 본격적인 코드를 짜자.
무작정 단순 BFS를 짜지 않고, 조건에 따라서 일부 상황은 버릴 수 있도록 코드를 작성할 것이다.

탐색 속도를 위해서 리스트가 아닌 데크와 집합 구조를 사용했다.
데크에서 .popleft()를 수행해서 다음 방문할 위치를 뽑아낸다.
집합의 경우 현재까지 방문한 위치를 보관하며, 집합에다 in 연산을 수행하면 O(1)의 복잡도를 지니므로 빨리 접근이 가능하다.

while True:
    nowPos, movement = willVisit.popleft()  # 현재 위치 & movement
    if nowPos == K: break  # 도착 시

    if 0 <= nowPos-1 <= 100000 and not(nowPos-1 in visited):
        willVisit.append((nowPos-1, movement+1))
    if 0 <= nowPos+1 <= 100000 and not(nowPos+1 in visited):
        willVisit.append((nowPos+1, movement+1))
    if 0 <= 2*nowPos <= 100000 and not(2*nowPos in visited):
        willVisit.append((2*nowPos, movement+1))

    # 방문 표시
    visited.add(nowPos)

너비 우선 탐색 부분의 코드만 설명하려 한다.
우선, 데크 willVisit에 저장할 정보는 튜플 (다음 방문할 위치, 현재까지 movement) 정보가 되겠다.
이를 .popleft()한 다음, 만일 현재 위치가 도착 지점이면 break하면 된다.
그게 아닌 경우엔 조건에 따라서 각각의 다음 방문 위치를 willVisit에 .append()해주면 된다.

방문 가능 조건은 크게 2가지를 고려하면 된다.
첫 번째는 방문할 좌표의 위치가 valid한가? (0에서 100000 사이의 값인가?) 0 <= 위치 <= 100000
두 번째는 현재까지 방문한 적 없는 위치인가? not(위치 in visited)
이 두개를 and연산 취한 다음 둘다 맞는 경우 .append()해주면 된다.
최종 출력은 break했을 때의 movement값이 된다.

아래는 전체 코드이다.

from collections import deque

N, K = map(int, input().split())

willVisit = deque([(N, 0)])  # 다음 방문할 장소 & movement
visited = set() # 이미 방문한 위치

while True:
    nowPos, movement = willVisit.popleft()  # 현재 위치 & movement
    if nowPos == K: break  # 도착 시

    if 0 <= nowPos-1 <= 100000 and not(nowPos-1 in visited):
        willVisit.append((nowPos-1, movement+1))
    if 0 <= nowPos+1 <= 100000 and not(nowPos+1 in visited):
        willVisit.append((nowPos+1, movement+1))
    if 0 <= 2*nowPos <= 100000 and not(2*nowPos in visited):
        willVisit.append((2*nowPos, movement+1))

    # 방문 표시
    visited.add(nowPos)

print(movement)

BFS를 어떻게 구현해야 할지와 조금 더 효과적으로 탐색하기 위한 일종의 가지치기 과정을 결합하면 제한 조건 내로 풀 수 있는 문제였다.
사실 저 코드로 통과는 가능하지만, 메모리나 시간 측면에서 꽤 많이 잡아먹게 된다.
따라서, 추가로 찾아보니 이보다 더 효율적으로 코드를 짤 수 있는 방식도 있긴 했다.
가령 여기선 set을 썼지만 dict를 쓰는 방식도 있고, 아예 for문의 형태에 값을 저장한 방식도 있었다.
PyPy3로 제출해서 조금 더 빠른 통과가 가능했다는 내용도 있었다.

아무튼 같은 BFS 문제라도 완전히 다르게 구현할 수 있다는 게 신기하다 느껴졌다.