난이도

Gold 4

풀이 참고 유무

?

막힌 부분

1. 경로가 같더라도 접근 방식이 다르면 다른 경우로 인식해야함

문제

문제 바로가기

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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
2

문제 검토

x-1, x+1, 2*x 방향으로 넓게 탐색할 수 있다.
단 n이 100,000이므로 방문처리를 하도록 하여 메모리와 시간을 줄여보자.

또한 첫방문이 아니라 재방문일 경우에도 방문의 깊이가 같다면 방문할 수 있도록 만들어보자.

풀이(python)

Python

from sys import stdin
from collections import deque
n,k = map(int,stdin.readline().split())
visited = [0 for _ in range(1000001)]
cnt=0

if n==k:
    print(0)
    print(1)
    exit()

def BFS():
    global cnt
    q=deque()
    q.append(n)        
    
    while q:
        su=q.popleft()
        move=[su+1,su-1,su*2]        
        if su==k:
            cnt+=1      
        for mv in move:
            if mv>100000 or mv<0:
                continue
            if visited[mv] != 0 and visited[mv]!=visited[su]+1:
                continue
            else:
                visited[mv]=visited[su]+1
                q.append(mv)
BFS()
    
print(visited[k])
print(cnt)

이전 숨바꼭질1 문제와 다른 점은 visited[mv]!=visited[su]+1 이 조건이라고 보면 된다.
만약 이동했을 때 방문의 깊이가 같다면 재방문을 허용해주는 조건이다.

걸린 시간

19:56

총평

처음에 경로가 같으면 하나의 경우의 수로 인식하고 문제를 풀었다가 32퍼센트에서 계속 오답이 났다.
주어진 문제를 이해하기 위해 풀이를 조금 보게 되었다.

BFS에서 재방문을 할 때 이런 방식이 사용된다는 것을 알고 있자.