티스토리 뷰

알고리즘/백준

13549번 숨바꼭질3 백준 파이썬

글을 쓰는 개발자 2020. 12. 14. 18:15
반응형

문제:www.acmicpc.net/problem/13549

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
from collections import deque
def solve(visited,n,k):
    queue=deque()
    queue.append(n)
    travel[n]=True
    while queue:
        x=queue.popleft()
        if x==k:
            print(visited[x])
            return
        nx=set() #중복제거
        nx.add(x+1)
        nx.add(x-1)
        nx.add(x*2)
        for t in nx:
            if 0<=t<100001 and visited[t]==0:
                if t==x*2 and not travel[t]:
                    visited[t]=visited[x]
                    travel[t]=True
                   queue.appendleft(t) #우선순위 부여
                else:
                    if visited[t]==0 and not travel[t]:
                        visited[t]=visited[x]+1
                        travel[t]=True
                        queue.append(t)
 
n,k=map(int,input().split())
visited=[0]*100001
travel=[False]*100001
solve(visited,n,k)
cs

이 문제의 경우는 숨바꼭질에서 2배 이동한 경우는 시간이 0초라는 조건이 붙혀진 문제이다.

나는 이문제를 풀기위해 2배이동하는 것을 우선순위를 두기 위해 deque에서 appendleft를 했다. 이러면 2배로 이동한 좌표들이 먼저 확인되기 때문에 가장 빠른 시간을 추적할 수가 있다. 또한 x-1,x+1,x*2의 값이 겹치는 것을 우려하여 set()에 중복제거를 한 후 반복문을 돌렸다.

 

반응형
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함