[파이썬] 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 

5 17

예제 출력 1 

4 2

 

 

👧 나의 풀이

 

# 시간 초과
import sys

input = sys.stdin.readline
N, K = map(int, input().split())  # 수빈 위치, 동생 위치
dp = [K]
ans = 0
while N not in dp:
    ans += 1
    temp = list()
    for k in dp:
        temp.append(k - 1)
        temp.append(k + 1)
        if k % 2 == 0:
            temp.append(k // 2)
    dp = list(set(temp))

print(ans)
print(dp.count(K)*2)

 

시간 초과가 나서 bfs로 구현했다.

 

# 메모리 초과
import sys
from collections import deque

input = sys.stdin.readline
N, K = map(int, input().split())  # 수빈 위치, 동생 위치


def que():
    dp = deque([(K, 0)])
    while dp :
        pos, cnt = dp.popleft()
        if pos == N:
            if N in dp :
                ans=dp.count(N)*2
            else:
                ans=2
            return cnt, ans
        dp.append((pos - 1, cnt+1))
        dp.append((pos + 1, cnt+1))
        if pos % 2 == 0:
            dp.append((pos // 2, cnt+1))

print(*que(), sep='\n')

 

K에서 N을 만들었다.

경우의 수 어떻게 구할지 몰라서 임의로 N의 갯수를 구하고 *2했다 ㅠㅠ

 

# 실패
import sys
input=sys.stdin.readline

answer=0        # 동생을 찾는 방법의 수
N, K=map(int, input().split())      # 수빈이 위치, 동생 위치
n=[set() for _ in range(100001)]
n[0].add(N)
x=[1, -1, 2]

for i in range(1, 100001) :
    for j in n[i-1] :
        for dx in x :
            if dx != 2 :
                n[i].add(j+dx)
            else :
                n[i].add(j*2)
    if K in n[i] :          # 동생 위치
        answer=i
        break

print(answer)

dp로 구현

인덱스는 시간, 값은 수빈이의 위치 set

 

 

👼 다른 사람 풀이

# https://it-garden.tistory.com/345
import sys
from collections import deque
input = lambda : sys.stdin.readline().strip()

def bfs(n) :
    de=deque()
    de.append(n)
    ch[n][0]=0  # 시간
    ch[n][1]=1  # 경우의 수

    while de :
        x=de.popleft()

        for i in (x+1, x-1, x*2) :
            if 0 <= i < 100001 :
                if ch[i][0] == -1 :     # 처음 들르는 경우
                    ch[i][0]=ch[x][0]+1
                    ch[i][1]=ch[x][1]
                    de.append(i)
                elif ch[i][0] == ch[x][0]+1 :   # 한 번 이상 들르는 경우
                    ch[i][1]+=ch[x][1]          # 방법 더하기

n, k=map(int, input().split())
ch=[[-1, 0] for i in range(100001)]

bfs(n)
print(ch[k][0]) # 가장 빠른 시간
print(ch[k][1]) # 방법의 수

bfs로 구현

경우의 수와 시간은 dp

처음 들르면 움직이기 전 위치의 경우의 수를 넣는다.

한 번 더 방문하면 움직이기 전 방법의 수를 더한다.

 

 

# https://dailyheumsi.tistory.com/51
import sys
from collections import deque

n, k=list(map(int, sys.stdin.readline().split()))

def bfs(n, k) :
    # n : 시작지점, k : 도착지점

    # 바로 처리할 수 있는 경우 2가지
    if n == k :
        return 0, 1
    if n > k :
        return n-k, 1   # 후진 밖에 없음

    # visited[j] : j까지 오는데 얼마의 최소 time을 저장
    # ways[j] : j까지 최소 time으로 오는 방법의 수 저장
    q, visited, ways=deque([n]), [float('inf')]*100001, [0]*100001
    time, count, success=0, 0, False
    ways[n]=1
    visited[n]=0

    while q and not success :
        size=len(q)

        for _ in range(size) :
            cur=q.popleft()

            next_move=[cur-1, cur+1, cur*2]
            for j in next_move :
                if j >= 0 and j <= 100000 and time+1 <= visited[j] :
                    ways[j]+=1
                    visited[j]=time+1

                    if j == k :
                        success=True

                    if not success :
                        q.append(j)

        time+=1

    return visited[k], ways[k]

time, count=bfs(n, k)
print(time)
print(count)

bfs로 구현

위랑 알고리즘이 같음

위치 j가 0 이상 100000 이하이고 j 위치에서 시간이 time+1 이상이면 경우의 수, 시간을 늘리고 q에 추가한다.

 

 

# https://alpyrithm.tistory.com/103
from collections import deque

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

def solve(n, k) :
    if n >= k :
        print(n-k)
        print(1)
        return
    dx=[2, 1, -1]
    que=deque([(n, 0)])
    check=[0 for _ in range(100001)]        # 시간
    count=0         # 경우의 수
    while que :
        idx, cnt=que.popleft()      # 위치, 시간
        if idx == k :
            if not check[idx] :
                check[idx]=cnt
                count+=1
            else :
                if cnt == check[idx] :
                    count+=1
        for i in dx :
            if i == 2 :
                new_idx=idx*i
            else :
                new_idx=idx+i

            if 0 <= new_idx <= 100000 :
                if check[new_idx] == 0 or check[new_idx] >= cnt+1 :
                    if check[k] and cnt+1 > check[new_idx] :
                        continue
                    check[new_idx]=cnt+1
                    que.append((new_idx, cnt+1))

    print(check[idx])   # 시간
    print(count)    # 경우의 수
    return

solve(n, k)

동생이(k) 수빈이(n)보다 뒤에 있으면 뒤로 걸어가는 방법밖에 없다.

 

 

 

 

문제 출처 👉 백준