티스토리 뷰
반응형
문제:www.acmicpc.net/problem/13549
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()에 중복제거를 한 후 반복문을 돌렸다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
14226번 이모티콘 백준 파이썬 (0) | 2020.12.15 |
---|---|
13913번 숨바꼭질 4 백준 파이썬 (0) | 2020.12.14 |
1697번 숨바꼭질 백준 파이썬 (0) | 2020.12.14 |
2146번 다리 만들기 백준 파이썬 (0) | 2020.12.13 |
16964번 DFS 스페셜 저지 백준 파이썬 (0) | 2020.12.12 |
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- docker-compose
- django
- PostgreSQL
- DRF
- Python
- postgres
- 프로그래머스
- Pattern
- ubuntu
- thread
- Celery
- 백준
- 카카오
- docker
- Spring
- 2021 KAKAO BLIND RECRUITMENT
- dockerignore
- Java
- Linux
- headers
- 면접
- 알고리즘
- Collections
- 그래프
- env
- BFS
- setattr
- Command Line
- 파이썬
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함