Notice
Recent Posts
Recent Comments
Link
취준생의 코딩테스트 연습기
[백준] 1697번 숨바꼭질 / 파이썬(python) 본문
# 문제 링크
https://www.acmicpc.net/problem/1697
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
# Soultion
최소 시간을 구하기위해 bfs를 사용하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from collections import deque
n,k = map(int,input().split())
queue = deque([n])
visited = [0]*100001
visited[n]=1
while(queue):
a = queue.popleft()
if a==k:
print(visited[a]-1)
break
if 2*a<=100000 and visited[2*a]==0:
queue.append(2*a)
visited[2*a] = visited[a]+1
if a+1<=100000 and visited[a+1]==0:
queue.append(a+1)
visited[a+1] = visited[a]+1
if a-1>=0 and visited[a-1]==0:
queue.append(a-1)
visited[a-1] = visited[a]+1
|
cs |
4. bfs를 사용하기위해 queue를 생성한 뒤, 나의 위치를 넣어준다.
5. 위치별 최소시간을 보기위해 리스트 생성
6. 현재 나의 위치에 1을 넣어준다.
10. 만약 현재위치가 동생의 위치이면, 최소거리를 출력한다.
14 ~ 22. 2배, -1, +1의 경우를 각각 계산한다.
'코딩테스트 > 백준' 카테고리의 다른 글
| [백준] 10816번 숫자 카드 2 / 파이썬(python) (0) | 2021.05.21 |
|---|---|
| [백준] 1920번 수 찾기 / 파이썬(python) (0) | 2021.05.21 |
| [백준] 7569번 토마토 / 파이썬(python) (0) | 2021.05.20 |
| [백준] 2178번 미로 탐색 / 파이썬(python) (0) | 2021.05.19 |
| [백준] 1012번 유기농 배추 / 파이썬(python) (0) | 2021.05.19 |
Comments