[백준13913] / 숨바꼭질 4 - BFS

 

백준13913

 

푼 날짜 : 2024.10.18

푼 문제 : [13913] / 숨바꼭질 4

사용한 언어 : python

알고리즘 : BFS

 

 

접근 방식 :

가장 빠른 시간을 출력하는 것은 사실 이전과 비슷한 문제이기 때문에 어렵지 않았다.

중요한 것은 이동 방법이 여러개인데 이를 어떻게 출력할 것인가 였다!

 

내가 결정한 방법은

1) 이동 방법과 이동했을 때 위치를 저장

2) 도착지점에서 세 가지 이동 방식을 활용해서 출발지점으로 이동하는 방법을 찾기 -> stack에 추가

3) 출력을 pop을 사용해서 해준다

였다.

 

사실 여러가지 이동 방법 중 하나의 이동 방법만 출력하면 되기에 가능한 시도였던 것 같다.

 

 

코드 :

from collections import deque

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

# 방문 처리
visited = {}
# 이동 방향
dx = ['-', '+', '*']

queue = deque([N])
visited[N] = 0

move = []
while queue:
    now = queue.popleft()
    if now == K: break

    for i in dx:
        nx = now
        if i == '-': nx -= 1
        elif i == '+': nx += 1
        else: nx *= 2

        if 0<=nx<10**6+1 and nx not in visited:
            visited[nx] = visited[now] + 1
            queue.append(nx)
			
            # 이동 방법을 계산하기 위함
            if nx == now-1: move.append(('-', nx))
            elif nx == now+1: move.append(('+', nx))
            else: move.append(('*', nx))

move = move[::-1]

now = K # 도착 위치 -> 시작 위치 계산을 위함
answer = []
for i in move:
    if i[1] != now: continue
    answer.append(now)

    if i[0] == '-': now += 1
    elif i[0] == '+': now -= 1
    else: now = int(now/2)

answer.append(now) # 처음 시작 위치 추가

# output
print(visited[K])
while answer: print(answer.pop(), end=' ')
print()

 

 

 

사실 이렇게 하는게 맞나 조금 의심은 들지만.. 성공 !!!

뿌듯 !