[백준(BOJ)] 1697번 : 숨바꼭질 - PYTHON[파이썬]

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

---

 

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

오늘 스터디에서 공부한 BFS를 적용해서 풀었다.

BFS는 Breadth First Search이다. 넓이 우선 탐색, 그래프 탐색 중 하나이다.

 

가장 짧은, 가장 빠른과 같은 것을 물어보면 BFS를 생각하자.

그리고 파이썬에서 queue는 반드시 deque를 사용해야 한다.

queue는 매우 느리고 시간 초과의 원인이다.

 

짚고 넘어가자!

queue와 deque는 비슷하지만 명확한 차이점이 있다.

• queue는 한쪽으로만 입력 가능, 반대쪽으로만 출력 가능
• deque는 양쪽으로 입출력 가능

 

그렇다면 문제에서 말한 5->17을 예로 문제에 접근해보자

1초 후에는 현 위치에서 1을 더하거나, 1을 빼거나, 2를 곱하는 점에 대해 이동하거나 순간이동할 수 있다.

 

시작점이 5, 도착점 17

0초에 갈 수 있는 수는 1

1초 : 4, 6, 10 (5-1, 5+1, 5*2)

2초 : 3, 7, 8, 9, 11, 12, 20 (수가 점점 많아진다)

3초 : ,.... 16,......,40 (생략)

4초 : 17,,,,32,,,(생략)

 

이러한 로직으로 돌아간다.

---

 

⊙ 문제 풀이

 

import sys
from collections import deque
input = sys.stdin.readline()

def bfs():
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        if x == k:
            print(dist[x])
            break

        for j in (x-1,x+1,x*2):
            if 0<= j <= MAX and not dist[j]:
                dist[j] = dist[x] +1
                q.append(j)

MAX = 100000
n,k = map(int,input.split())
dist = [0] * (MAX+1)

bfs()

 

MAX를 설정한 이유는 N과 K의 제한사항이 0에서부터 100,000이기 때문이다.

그다음 n, k 값을 입력받고 dist라는 배열을 최대수만큼 생성하고 0으로 초기화한다.

 

그리고 def로 정의된 bfs()를 돌리게 된다.

 

bfs를 뜯어보자

 

1. 큐를 빠르게 해 주기 위해 q = deque()를 설정해주었다.
2. 그다음 첫 번째, 수빈이가 있는 위치 N(출발점)을 넣어준다.
3. while문을 돌려 q가 정수일 때 계속 반복시켜준다.
4. 제일 왼쪽 값을 pop, 그리고 그 값을 x에 저장
5. 만약 그 x의 값이 동생이 있는 위치 k일시 dist [x]를 출력하고 프로그램 종료
6. for문을 돌린다. x-1, x+1, x*2의 값을 j에 순서대로 넣어준다.
7. 만약 j의 값이 0과 MAX 사이의 값이고 dist [j]가 0의 값을 가질 시 dist [x]+1을 해주고 j를 추가
8. 값을 찾을 때까지 반복

아래에 5->17로 예를 들어보자

 

x = 5, j = 4, 6, 10

4, 6, 10은 0과 MAX 사이의 값 dist [4, 6, 10] = dist [5] + 1 = 0 + 1 = 1

 

x = 10으로 바로 넘어가면 j = 9, 11, 20

9, 11, 20은 0과 MAX 사이의 값 dist [9, 11, 20] = dist [10] + 1 = 1 + 1 = 2

 

dist [10]= 1인 이유는 위 x=5일 때 1이 추가되었다.

 

x = 9, j = 8, 10, 18

8, 10, 18은 0과 MAX 사이의 값 dist [8, 10, 18] = dist [9] + 1 = 2 + 1 = 3

 

x = 18, j = 17, 19, 36

17, 19, 36은 0과 MAX 사이의 값 dist [17, 19, 36] = dist [18] + 1 = 3 + 1 = 4

 

위 def bfs 5번 문항인 만약 그 x의 값이 동생이 있는 위치 k일시 dist [x]를 출력하고 프로그램 종료를 만족

 

따라서 5->17은 4가 출력된다.

---

 

⊙ 결과

 

 

---

⊙ 마무리

 

 

파이썬에서 queue는 반드시 deque를 사용해야 한다.

 

좋아요는 로그인하지 않아도 누를 수 있습니다!