백준 파이썬 13549 문제

문제)

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

13549번: 숨바꼭질 3

감각을 찾기위해 오랜만에 알고리즘을 풀었지만 접근도 잘못했다.

숨바꼭질같은 문제를 dfs로 푼 기억이 있어 dfs로 풀려했지만 풀리지 않아 다른 분들의 풀이를

보니 이 문제에서 가중치가 다르다는 걸 인지를 못하고 있었다.

 

나의 잘못된 풀이)

import math
import sys

ans = math.inf
visited = []
n, k = map(int, input().split())

stack = [(n,0)]
while stack:
    temp, time = stack.pop()
    if temp == k:
        if ans >= time:
            ans = time
            continue

    if temp not in visited:
        if 0 <= temp <= 100000:
            if temp > k:
                dif = temp - k
                stack.append((temp-dif, time+dif))
            else:
                stack.append((temp+1, time+1))
                stack.append((temp-1, time+1))
                stack.append((temp*2, time))
            visited.append(temp)
    #print(stack, ans)

#print(visited)
print(ans)

else: 부분에 stack.append 3개 연속으로 한 부분이 깔끔하지 않은 것 같다. 

앞으로는 for i in [temp+1, temp-1, temp*2] 라는 표현이 더 깔끔할 것 같다.

visited도 나는 숫자를 넣어 들어간건지 안한건지를 체크했는데 그런 방식도 괜찮지만

초기화한 배열에 인덱스를 위치라고 생각하고 값을 그 위치에 가는데 걸린 시간으로 표현한

것도 좋은 것 같다.

 

bfs로 푸신 분들은 가중치가 달라서 deque를 활용했다. 0초로 순간이동하니 가중치가 더 높아

큐에서 왼쪽부터 빼낼 때 순간이동한 것들을 왼쪽에 추가해 먼저 빼도록 해준 것 같다.

+1이나 -1은 가중치가 순간이동보다 낮으니 추가를 오른쪽부터 해주었고...

 

다익스트로 푸신 분들도 있는데 다익스트라를 다시 공부해봐야 할듯.