[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1697번 & 12851번 _ 숨바꼭질 1, 2

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

https://www.acmicpc.net/problem/12851

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는 정수이다.

[출력]

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

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

 

[아이디어]

1) 숨바꼭질 1은 가장 빠른 시간만, 2는 찾는 방법의 수까지 출력하면 된다.

2) queue에 숫자들을 두고 관리하면서, 동생의 위치가 나오면 break한다.

3) 동생을 최소의 횟수로 찾았을 때만 방법의 수를 더해가면서, 처음으로 동생의 위치가 pop되면 return 하되, queue에 동생의 위치가 남아있다면 그만큼 숫자를 더해줘야 방법의 수가 출력된다.

 

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

# 숨바꼭질 1
from collections import deque
cnt = [0 for _ in range(100001)]
q = deque([n])
while q:
    tmp = q.popleft()
    if tmp == k:
        break
    for x in [tmp-1,tmp+1,tmp*2]:
        if 0<=x<=100000 and cnt[x]==0:
            cnt[x] = cnt[tmp] + 1
            q.append(x) 
print(cnt[k])

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

# 숨바꼭질 2
from collections import deque
cnt = [[0,0] for _ in range(100001)]
q = deque([n])
while q:
    tmp = q.popleft()
    if tmp == k:
        cnt[k][1] = 1 + q.count(k)
        break
    for x in [tmp-1,tmp+1,tmp*2]:
        if 0<=x<=100000 and cnt[x][0]==0:
            cnt[x][0] = cnt[tmp][0] + 1
            cnt[x][1] += 1
            q.append(x) 
        elif 0<=x<=100000 and cnt[tmp][0] +1 == cnt[x][0]:
            cnt[x][1]+=1
            q.append(x)       
print(*cnt[k],sep = '\n')

1의 방법을 살리려다보니 약간 비효율적인 코드가 써진 것 같은데, q에서 하나씩 pop하는게 아니라 while문의 반복마다 안에서 for문을 돌리면 걸리는 시간이 n초인 모든 경우를 관리할 수 있기 때문에 많은 분들이 그렇게 푸신 것 같다.