백준 12851번: 숨바꼭질 2 Python 풀이 및 정답 코드

문제 링크

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

출력

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

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

 

 

 

문제 풀이

bfs 문제같았는데 bfs 너무 싫어서 일단 dfs 재귀로 빠르게 풀어봤다.

from collections import deque
import sys

sys.setrecursionlimit(10000)

N, K = map(int, input().split())

min = 100000
count = 0

def dfs(x, time):
    global min, count
    if x == K:
        if time < min:
            min = time
            count = 1
        elif time == min:
            count = count + 1
        return
    if time > min:
        return
    dfs(2 * x, time + 1)
    dfs(x + 1, time + 1)
    dfs(x - 1, time + 1)

dfs(N, 0)

print(min)
print(count)

예제는 잘 돌아가는데 문제는 1 100 이런 케이스에 너무 오래 걸린다. 심지어 dfs(x - 1, time + 1)이 부분을 세개 중에 제일 위로 올려주면 아예 음수로 뚫고 들어가버린다.
여려모로 dfs로 풀면 안될 것 같아서 bfs로 풀기로 함.

최단 시간만 구하는게 아니라 최단거리 경우의 수까지 구해야 하므로 visited를 이중배열로 사용해서 [도착한 최단 시간, 최단시간 경우의 수]를 저장했다. visited[N] = [0, 1]로 시작한다.

1. visited를 이중배열로 사용해서 [도착한 최단 시간, 최단시간 경우의 수]를 저장했다. visited[N] = [0, 1]로 시작한다.
2. 이미 구해진 최단 시간보다 더 조사하지 않는다.
3. 방문한 적 없는 위치일 때만  queue에 넣어준다.
4. 이 위치에 이전에 방문한 적이 있고 현재 도달한 시간이 최단 시간이면 최단 거리인 경우의 수가 늘어나는 것이므로 바로 이전 위치까지의 경우의 수와 더해준다.

총 세번 틀렸는데, 아래가 로직 검증하기 좋은 반례이다.

100000 0
100000
1

1 10
4
2

5 237
10
5

 

 

 

코드

from collections import deque

N, K = map(int, input().split())

q = deque([N])
# [최단 시간, 최단시간으로 방문한 횟수]
visited = [[-1, 0] for _ in range(100001)]
visited[N][0] = 0
visited[N][1] = 1

while q:
    x = q.popleft()
    if visited[K][0] != -1 and visited[x][0] > visited[K][0]:
        break
    for a in [x - 1, x + 1, 2 * x]:
        if 0 <= a <= 100000:
            # 방문한 적 없는 위치일 때
            if visited[a][0] == -1:
                q.append(a)
                visited[a][0] = visited[x][0] + 1
                visited[a][1] = visited[x][1]
            # 방문한 적 있는 위치이고 현재 여기까지 도달한 시간이 최단 시간일 때
            elif visited[x][0] + 1 == visited[a][0]:
                visited[a][1] += visited[x][1]

print(visited[K][0])
print(visited[K][1])

 

 

 

결과

 

 

 

다른 사람의 코드

다음 블로그를 참고함

https://velog.io/@dhelee/%EB%B0%B1%EC%A4%80-12851%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%884-Python-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS

[백준] 12851번: 숨바꼭질4 / Python / 너비우선탐색(BFS)

 

 

 

리뷰

어려웠다

구현은 어렵지 않았지만 직관에 의지해 풀기엔 반례가 너무 많았다.
통과 여부를 확인할 수 없는 코테였으면 맞히기 쉽지 않을 듯,,,