BOJ 1697번: 숨바꼭질

호프 2021. 2. 6. 03:47

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

아이디어:

앞선 A->B 문제와 비슷한 방식으로 그래프를 구현하여 풀 수 있을 것 같다. 대신 이번 문제는 무조건 BFS로 풀어야 한다.

생각해야 할 조건이 많아서 예상외로 까다로웠다.

처음에 그냥 제출하니 메모리 초과가 났고.. 그래서 한 번 만든 수를 다시 만들지 않도록 visit 배열을 추가했다. 예를 들면 *2를 하여 이미 한번의 경로만을 사용하여 만든 수를 +1 두번을 사용하여 같은 수를 다시 만드는 것은 불필요하기 때문이다.

그리고 나니 인덱스에러가 생겼는데, n[0]의 범위가 주어진 좌표의 범위를 넘어서는 경우가 발생할 수 있기 때문이었다. 따라서 조건에 그것도 추가했더니 통과했다.

import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
q = deque()
q.append([N, 0])
#메모리 초과를 줄이기 위해.. 쓸데없는 연산 제거.
visit = [False]*100001
while(q):
    n = q.popleft()
    if (n[0]==K):
        print(n[1])
        sys.exit(0)
        
    if (n[0]<=100000 and n[0]>=0 and visit[n[0]]==False):
        visit[n[0]]=True
        q.append([n[0]*2, n[1]+1])
        q.append([n[0]-1, n[1]+1])
        q.append([n[0]+1, n[1]+1])