[Baekjoon] 12851_숨바꼭질 2

Gold V

문제(출처: https://www.acmicpc.net/problem/12851)

---

<숨바꼭질 2>

문제 

 

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

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

 

 

입력

 

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

 

출력 

 

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

 

문제 풀이

 

 - my solution (Python)

import sys
from collections import deque

if __name__=='__main__':
    x,y=map(int,sys.stdin.readline().split())

    answer=[0]*100001
    queue=deque([x])

    cnt=0
    if x==y: # 현재 위치와 도착할 위치가 같다면
        cnt=1
    else:
        while queue:
            temp=queue.popleft()
            dx = [temp-1, temp+1, temp*2] # 1초 후 
            for x in dx:
                if x>=0 and x<=100000 : # 점 범위
                    if answer[x]==0 or answer[x]>=answer[temp]+1:
                        if x == y and answer[x] == answer[temp] + 1: # 방법의 수
                            cnt += 1
                        elif x==y and (answer[x]>answer[temp]+1 or answer[x]==0): # 가장 빠른 시간
                            cnt=1
                        answer[x]=answer[temp]+1
                        queue.append(x)
    print(answer[y]) # 가장 빠른 시간
    print(cnt) # 가장 빠른 시간으로 찾는 방법의 수

 

저번에 해결했던 1697 숨바꼭질 문제와 매우 비슷한 문제이다.

하지만 이 문제에서는 방법의 수를 함께 구해야 하므로 코드를 고쳐야 했다.

 

• 현재 위치, 도착해야 할 위치 입력
• answer = 시간
• cnt = 가장 빠른 시간으로 찾는 방법의 수
• 현재 위치와 도착해야 할 위치가 같다면 -> 가장 빠른 시간 = 0, 가장 빠른 시간으로 찾는 방법의 수 =1
• 현재 위치와 도착해야 할 위치가 같지 않다면 -> queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> 이동하려는 위치가 범위 안 -> 아직 그 위치를 한 번도 방문하지 않았으며 ( answer [x] =0 ) 빠른 시간이라면 (answer [x]>=answer [temp]+1) -> 도착 위치이며 가장 빠른 시간이면 cnt +1 but 도착 위치이며 빠른 시간 갱신이면 cnt =1 / 앞의 두 조건과 상관없이 answer 값 update 및 queue에 추가
• 가장 빠른 시간 ( answer [y] ), 가장 빠른 시간으로 찾는 방법의 수 ( cnt ) 출력

 

❓ 처음에 왜 틀렸는가?

똑같은 길로 가는 경우를 고려하지 못하였다. 예를 들어 1 3이 입력으로 들어오면 2 2 가 출력되어야 한다. 1 + 1 +1 , (1 * 2) +1과 같이 2가지의 경우가 있기 때문이다. 하지만 첫 번째 제출한 코드로는 한번 방문했던 곳은 다시 가지 못해 1에서 2로 가는 경우를 한 가지 경우가 나오도록 구현하였기 때문이다. 

 

❓ 두 번째는 왜 틀렸는가?

입력받을 때 x와 y 값이 같은 경우를 처리해주지 못하였다. 처음에 틀렸을 때 x와 y가 같은 경우를 생각해봤지만 내가 구한 값이 맞는 줄 알았다. 아무리 다른 예제를 입력해도 맞다고 생각하여 찾아보니 x와 y 값이 같을 때 가장 빠른 시간으로는 0초, 방법의 수로는 1이 나와야 한다는 것이었다. 0초가 가능한지는 몰랐다.... 그래서 while문 다음에 x와 y 값이 같은 경우 처리해주었더니 또 틀려 이 문제가 아닌 줄 알았다. 하지만 한참 찾아보니 x와 y가 같은 경우의 조건문을 잘못된 위치에 넣어서 해결하지 못한 것이었다.

 

---

생각🤔

 

경로가 여러 가지인 경우를 구하는 방법은 혼자서 잘 해결하여 뿌듯해하고 있었는데...

x와 y가 같은 경우 0초.. 0 초라니..

 

---