[Python] 백준 1697번 문제, 숨바꼭질

<문제 링크>

 

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

1697번: 숨바꼭질

 

---

<풀이>

 

이 문제는 너비 우선 탐색입니다. 그런데 입력을 그래프가 아닌 시작점과 끝점만 입력을 받을까?

그래프 정보가 없기 때문에 직접 그래프를 만들어주면서 탐색을 진행해야 한다.

그럼 그래프는 어떻게 만들까?

현재 foucs 값을 현재 노드의 값으로 지정하고 가중치가 없는 3개의 간선을 갖는다.

그 간선의 노드 값들은 focus의 { -1, +1, *2 }한 값들이다.

 

예제 입력인 5, 17로 설명을 해보겠다.

그래프 시작이 5라고 했을 때 5와 연결된 건 { 4, 6, 10 }이다.

{ 4, 6, 10 }을 다시 BFS 큐로 넣어 4랑 연결된 노드를 리스트에 넣자

그럼 BFS que = [6, 10], Next que = [3, 8]이다.

그런데 왜 4+1인 5가 없을까?

왜냐하면 5가 큐에 들어온 적이 있기 때문에 check[5] = True가 됬기 때문이다.

그래서 4와 연결된 5와 큐에 들어가려고 했을 때 True이기 때문에 삽입이 안 됐다.

6을 focusing 할 때 Next que = [3, 8, 7, 12]가 되며, 10을 포커싱할 때 [3, 8, 7, 12, 9, 11, 20]이 된다.

이게 다시 BFS que로 되어 focus가 17일 될 때, return count를 하여 BFS que를 확인한 횟수를 리턴한다.

 

---

<코드>

strat, end: 시작점, 끝나는 점

check[]: BFS를 통해 한 번 확인된 숫자에 대한 중복을 막기 위한 Boolean

que[]: BFS의 현재 스택

next_que[]: 다음에 진행할 BFS 스택

focus: 현재 노드

count: 몇 초 후인지 확인하는 변수(result)

---

import sys

def bfs(start, end):
    que = [start]
    next_que = []
    count = 0

    while len(que) != 0:
        focus = que.pop(0)

        if focus == end: # break
            return count
        elif focus == 0: # 0일 경우 +1만 가능
            checking(focus + 1, next_que)
        elif focus == 100000: # 100,000일 경우 -1만 가능
            checking(focus - 1, next_que)
        elif focus * 2 > 100000: # 현재값 * 2가 범위를 넘어갈 경우
            checking(focus - 1, next_que)
            checking(focus + 1, next_que)
        else: # default
            checking(focus - 1, next_que)
            checking(focus * 2, next_que)
            checking(focus + 1, next_que)

        # 현재 스택이 끝나면 다음 스택으로 넘어감 and count++
        if len(que) == 0:
            que = next_que.copy()
            next_que = []
            count += 1

# 이미 한 번 확인한 숫자라면
def checking(num, next_que):
    if not check[num]:
        check[num] = True
        next_que.append(num)

if __name__ == "__main__":
    start, end = map(int, sys.stdin.readline().split())
    check = [False for _ in range(100001)] # 숫자 중복 확인 방지
    check[start] = True

    print(bfs(start, end))