[BOJ] 숨바꼭질 (no.1697)

wisepine·2021년 1월 22일
0

알고리즘

목록 보기
40/83

문제

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

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

입력

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

출력

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


원래는 숨바꼭질 4를 풀려고 했었는데,
도저히 잘 되지가 않아 숨바꼭질 1부터 풀어보는걸로.

이번 풀이는 과정이 좀 많다. 험난하다...
솔브까지 약 4트 정도 하고 개선 풀이까지 있다.

🤔 생각

  • 프로그래머스(점프와 순간이동)에서 풀었던 문제와 매우 비슷하다.

  • 홀수/짝수로 뭔가 규칙이 존재할것이다 아마. 그게 가장 빠른 풀이 같긴 한데...

  • bfs를 공부할 목적이었으니 bfs를 사용해서 풀자!

📌 1차 풀이

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    q = deque()
    q.append((n,0))

    while q:
        x,cnt = q.popleft()
        if x == k: return cnt
        cnt += 1
        q.append((x-1, cnt))
        q.append((x+1, cnt))
        q.append((2*x, cnt))
    


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

오...
그렇게 무겁게 짰다고 생각하진 않았는데
생각해보니 방문 처리도 안 해줬고, 카운트는 대체 왜 큐에 같이 넣은거지..?
무의식적으로 dp처럼 처리하려 한 것 같은데 이건 그럴 필요가 없다.(어차피 같은 레벨이면 카운트도 같다)

일단 전부 고쳐주고, 메모리 문제엔 보약(?)인 비트마스킹으로 방문처리를 해봤다.

📌 2차 풀이 (비트마스킹)

import sys
input = sys.stdin.readline
print = sys.stdout.write


def bfs():
    q = [n]
    ans = 0
    cache = 0

    while q:
        tmp = []

        for x in q:
            if x == k: return ans

            if not cache & (1 << x-1): tmp.append(x-1)
            if not cache & (1 << x+1): tmp.append(x+1)
            if not cache & (1 << x*2): tmp.append(2*x)
        
        q = tmp
        ans += 1

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

내가 짰지만 참신하다

뭐가 참신해.

시간 초과... 그럴만도 하다. 메모리를 크게 절약하는 대신 매번 비트 연산을 해줘야한다.
비트 연산보다는 평범한 방문 리스트 인덱스 접근이 더 빠를 것이다.

그렇다면 방문 리스트를 만들어서 어떻게 되나 확인해보자.
중복해서 체크할 일이 없으니 리스트일 필요도 없고, 집합 형태로 하자.

📌 3차 풀이 (집합)

import sys
input = sys.stdin.readline
print = sys.stdout.write


def bfs():
    q = [n]
    ans = 0
    cache = 0
    cache = set()

    while q:
        tmp = []

        for x in q:
            if x == k: return ans

            if not cache & set({x-1}): 
                cache.add(x-1)
                tmp.append(x-1)
            if not cache & set({x+1}): 
                cache.add(x+1)
                tmp.append(x+1)
            if not cache & set({x*2}): 
                cache.add(x*2)
                tmp.append(x*2)
        
        q = tmp
        ans += 1

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


또??
내가 뭘 고려 안 한걸까.... 하다가 퍼뜩 떠오른게
n과 k에는 명시적인 범위가 있다.

처음에는 어차피 bfs로 하니까 답을 만나자마자 함수를 탈출 시킬 것이니, 범위 제한에 의미가 없다고 생각했는데...

경우의 수에 x+1이나 x-1만 있었으면 큰 상관이 없었을 것이다.
x*2가 있으니 범위를 크게 넘어간 값이 계속 큐잉되는 일이 생긴다...

이 부분이 영향을 끼쳤을거라 생각했고, 아래 최종풀이로 솔브했다.

📌 최종 풀이

import sys
input = sys.stdin.readline

def main():
    def bfs():
        q = [n]
        ans = 0
        cache = set()

        while q:
            tmp = []

            for x in q:
                if x == k: return ans

                if x-1 >= 0 and not cache & set({x-1}): 
                    cache.add(x-1)
                    tmp.append(x-1)
                if x+1 < 100001 and not cache & set({x+1}): 
                    cache.add(x+1)
                    tmp.append(x+1)
                if x*2 < 100001 and not cache & set({x*2}): 
                    cache.add(x*2)
                    tmp.append(x*2)
            
            q = tmp
            ans += 1

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

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

📌 개선 풀이 (리스트화)

import sys
input = sys.stdin.readline

def main():
    def bfs():
        q = [n]
        cache = [False]*100001
        ans = 0

        while q:
            tmp = []

            for x in q:
                if x == k: 
                    print(ans)
                    return

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

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

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

✔ 회고

  • 범위 제한은 웬만하면 해주자. 불필요한 조건문이 될지라도 최소 범위 초과로 인한 페일 때문에 머리 부여잡을 일은 없다... (풀고 나서 개선해주면 될일이다)
profile
글로 머리 정리하기

0개의 댓글