[백준 12851] 숨바꼭질 2 (python)

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

12851번: 숨바꼭질 2

숨바꼭질 2 문제

특정 지점에서 원하는 지점을 찾는 가장 빠른 시간이 몇 초 후인지와 가장 빠른 시간으로 찾는 방법의 갯수를 찾는 문제

딱 한 부분에서 막혀서 생각보다 원하는 형태로 답이 나오지 않아서 다른분의 코드 딱 한줄 참고해서 해결 할 수 있었다.

정답 코드

import sys
from collections import deque
N, K= map(int, sys.stdin.readline().split())
queue = deque()
queue.append(N)
way = [0]*100001 # 최대 크기
cnt, result = 0,0
while queue:
    a =  queue.popleft()
    temp = way[a]
    if a == K: # 둘이 만났을 때
        result = temp # 결과
        cnt += 1 # 방문 횟수 +1
        continue
    
    for i in [a-1, a+1, a*2]:
        if 0 <= i < 100001 and (way[i] == 0 or way[i]== way[a] +1): #범위 안에있고 방문하지 않았거나, 다음 방문이 이전 방문+1이면
            way[i] = way[a] + 1
            queue.append(i) 
print(result)
print(cnt)

원하는 지점에서 원하는 위치까지의 거리를 묻는 문제로 BFS의 개념을 활용하여 풀 수 있는 문제다.

a-1, a+1, a*2를 고려해서 범위 내에 있고, 방문하지 않았거나 방문했어도 이전 지점에서 재방문 할 수 있을 경우의 조건을 달아주었다.

그러고 K값이 됐을 때의 방문 거리와 방문 횟수를 저장해주었다. 이때 연산이 처음부터 돌아가야 하므로 continue를 넣어주었다. (넣지 않을경우 중간 테스트케이스에서 틀려버린다)

반응형

 

느낀 점

BFS를 활용하여 푸는 문제이다. 숨바꼭질 1의 경우 어렵지 않게 해결할 수 있었는데, 총 몇번인지까지 세는 방법을 찾으려다가 실패했다. 이전 지점에서 재방문 할 수 있는 경우를 아이디어로 떠올리지 못해서 애먹었는데, 저렇게 재방문을 할 수 있게 만드는 방법이 있다는 점을 다른사람의 코드를 참고하여 배울 수 있었다.

BFS를 단순하게 적용하는 것이 아니라 다양하게 시도 해볼 수 있는 좋은 문제였다.