[BOJ] 숨바꼭질 5 (no.17071)

wisepine·2021년 1월 23일
0

알고리즘

목록 보기
44/83

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.


매웠다ㅜㅜ..

🤔 생각

  • 한마디로 특정한 정점을 찾는게 아니라, 움직이는걸 추격한다는 소리.

  • 이러면 방문한 노드는 다시 방문하지 않는다는 룰이 무너진다.

  • 방문처리를 안 하면 그래프의 가지가 많아지긴 하겠지만.. 동일 레벨 노드만 다시 안 담도록 구분해주면 답은 나오겠다. 그런데...

  • 멋진 시간 제한을 가진 문제다.

  • 불길하지만 일단 당장 떠오르는건 위 아이디어 뿐이었다. 생각한대로 한번 짜보자...

📌 1차 풀이

import sys
input = sys.stdin.readline

def main():
    def bfs(n,k):
        q = [n]
        cache = [-1]*500001
        cache[n] = 0
        level = 0

        while q:
            tmp = []

            for x in q:
                if x == k: return level
                for i in (x-1, x+1, x*2):
                    if 0 <= i <= 500000 and cache[i] != level:
                        cache[x] = level
                        tmp.append(i)
            
            q = tmp
            level += 1
            k += level

        return -1

    n,k = map(int, input().split())
    print(bfs(n,k))

if __name__ == "__main__":
    sys.exit(main())

사실 시간 초과 날거 알고 있었다. ㅎㅎ
시간 제한이 타이트한걸 보면 돌파구가 있다는 뜻이고, 뭔가 발상의 전환이 필요한데... 잘 떠오르지 않아 검색해서 조금 힌트를 얻었다.
내 머리만으로 풀어야 시원한데 그러지 못해서 아쉽다. 😢


재방문이 가능하고, x+1와 x-1 노드 방문을 반복하는 그래프라면
같은 노드가 레벨마다 일정한 패턴으로 재방문 된다. +1과 -1을 더하면 0이니 당연하다!

손으로 큐를 그려보면, 홀수 번째 레벨에서 큐잉된 노드들은 그 다다음 레벨에서도 또 큐잉된다. (레벨 3에 있는 노드들은 5에서도 큐잉된다.)
짝수도 마찬가지다!

그렇다면, 굳이 모든 노드를 큐에 넣지 않아도 레벨의 홀짝 여부만 안다면, 어떤 노드들이 재방문할지 이미 알 수 있다.
그리고 앞서 방문된 노드들은 이미 탐색이 되고 있다. 또 큐잉하지 않아도 경우의 수가 생략될 염려는 없다.

이걸 필터링하지 않는다면 중복 순회를 한없이 하게 된다..

그렇다면 이걸 어떻게 처리할 것이냐

  • 홀짝 구분 방문 리스트!
  • 한 레벨마다 방문 리스트의 타겟 인덱스가 채워져있는지 확인하고, 채워져있다면 해당 레벨(문제로 치면 초수)에서 동생이 발견되었다는 뜻이므로 레벨을 리턴하면 된다.

📌 최종 풀이

import sys
input = sys.stdin.readline

def main():
    def bfs(n,k):
        q = [n]
        cache = [[False]*500001 for _ in range(2)]
        cache[0][n] = True
        flag = 0
        level = 0

        while q:
            if k > 500000: break
            if cache[flag][k]: return level

            tmp = []
            flag = 1 - flag
            for x in q:
                for i in (x-1, x+1, x*2):
                    if 0 <= i <= 500000 and not cache[flag][i]:
                        cache[flag][i] = True
                        tmp.append(i)
            
            level += 1
            k += level
            q = tmp

        return -1
    
    n,k = map(int, input().split())
    print(bfs(n,k))

if __name__ == "__main__":
    sys.exit(main())

✔ 회고

  • 맵지만 신박한 bfs 문제였다!
  • 재방문이 허용된 +1, -1 이동의 반복은 이전 노드가 홀짝별로 누적되어 큐잉되는 방식이다.
  • 다시 큐에 넣을 필요 없이, 홀짝 방문 리스트로 체크만 해주고 정해진 시간 안에 타겟 노드를 찾는데에만 집중하게 만든다.
profile
글로 머리 정리하기

0개의 댓글