[Baekjoon, Python] 1697번 : 숨바꼭질

도입

백준 단계별 풀기 DFS와 BFS 일곱 번째 문제이다.

백준 1697번 문제, 입력, 출력

---

백준 1697번 입출력 예제 1

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

풀이

1. 수빈이가 매 초마다 할 수 있는 행동은 -1, +1, *2 총 3가지이다. 매 초 마다 수빈이가 3가지를 수행하는 경우의 수를 펼칠 것이다. 예를 들어, 2초가 지난 시점에서 [-1 -1] 또는 [-1 *2] 등을 선택할 수 있을 것이다.

 

2. 다만, 무조건적으로 이 경우를 세어나가는 것이 아닌, 조건이 있다. 방문한 곳은 1값을 줘서 해당 위치는 방문을 했기 때문에, 추가적으로 셀 필요가 없다는 것을 알린다.

 

3. deque를 사용해서, queue가 비워질 때 까지, 해당 경우의 수들을 넣는데, 넣을 때, var_sec(몇 초가 지났는지)의 정보에 +1을 해서 넣는다.

 

4. 다음 예는 "5 14"를 입력으로 넣고, 각 if문, -1,+1,*2 마다 print(queue)를 하였을 때 볼 수 있는 콘솔창 결과이다. 예제처럼 "5 17"을 넣으려고 했지만 콘솔창의 길이가 너무 커져서 5 14로 하였다. 어떤식으로 돌아가는지 이해하기에는 충분하다.

입력 5 14 결과 3

---

 

코드

from sys import stdin
from collections import deque

def bfs(queue):
    while(queue):
        var_x, var_dept = queue[0][0], queue[0][1]
        if var_x == var_K:
            break
        queue.popleft()
        visit[var_x] = 1
        if var_x - 1 >= 0 and visit[var_x - 1] == 0:
            queue.append([var_x - 1, var_dept + 1])
        if var_x + 1 <= 100000 and visit[var_x + 1] == 0:
            queue.append([var_x + 1, var_dept + 1])
        if var_x * 2 <= 100000 and visit[var_x * 2] == 0:
            queue.append([var_x * 2, var_dept + 1])

var_N,var_K = map(int, stdin.readline().split())
visit = [0 for i in range(100001)]

queue = deque()
queue.append([var_N, 0])

bfs(queue)

print(queue[0][1])

---

마무리

새로운 접근이여서 신선했다. 또 하나를 알아가는 것 같아 매우 뿌듯하다.