관리 메뉴

차근차근

[백준 1697] 숨바꼭질 본문

대학교/Algorithm

[백준 1697] 숨바꼭질

SWKo 2020. 9. 6. 23:38

0. 제목

  • 백준 1697 숨바꼭질
  • BOJ 1697 숨바꼭질
  • 파이썬 1697 숨바꼭질
  • Python 1697 숨바꼭질

1. 문제

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

 

1697번: 숨바꼭질

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

www.acmicpc.net


2. 풀이

  • 현재 위치가 N이라고 할 때 이동가능한 지점은 N + 1, N - 1, 2*N 이다.
  • 가장 빠른 시간을 찾기위해 bfs를 사용한다.
  • 가장 먼저 현재 위치 좌표를 deque(덱, 큐의 앞과 뒤에서 삽입과 삭제가 가능한 큐)에 넣는다.
  • 큐가 빌 때까지 반복한다. 현재 위치를 q의 가장 왼쪽 요소로 갱신하며 탐색을 한다.
  • arr라는 배열을 선언하여 해당 지점까지 걸리는 시간을 값으로 가진다. arr[3] = 4 라면 3까지 가는데 4초가 걸린다는 의미이다.
  • 현재 위치에서 이동 가능한 값들 중 거리범주 내에 있고 방문하지 않았던 지점이라면 현재 지점까지 걸렸던 시간에서 1을 더해준다.
  • 방문한 점을 deque에 append로 추가해준다.
  • 현재 위치가 최종 목적지와 같아지게 되면 걸린 시간을 반환해주고 그 값을 출력한다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque
 
MAX = 100001
n, k = map(int, input().split())
arr = [0* MAX
 
def bfs():
    q = deque([n])
    while q:
        now_pos = q.popleft()
        if(now_pos == k):
            return arr[now_pos]
        for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
            if 0 <= next_pos < MAX and not arr[next_pos]:
                arr[next_pos] = arr[now_pos] + 1
                q.append(next_pos)
                
print(bfs())
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1012] 유기농 배추  (0) 2020.09.08
[백준 2606] 바이러스  (0) 2020.09.08
[백준 1260] DFS와 BFS  (0) 2020.09.05
[백준 2110] 공유기 설치  (0) 2020.09.04
[백준 1874] 스택 수열  (0) 2020.09.03
0 Comments
댓글쓰기 폼