[BOJ] 1697번 숨바꼭질 / 사용언어 : 파이썬(python)

※ 문제링크

1697번: 숨바꼭질

해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. BFS 구현을 위해 collections의 deque를 사용하였으며, 문제에서 주어진 이동조건을 구현하기 위해 간단하게 함수를 작성하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 N값을 deque리스트에 삽입하여주고, 이미 방문한 숫자들을 제외하기위해 방문여부를 확인할 배열을 작성해준다.

2. 이동할 수 있는 경우는 기본적으로 3개이기에 deque활용하여 3개의 값을 구한 후 다시 queue에 넣어준다.

3. K의 값이 queue에 들어갈 때까지 반복문을 통해 조건을 반복해주고, 반복횟수를 카운트해준다.

4. K의 값이 queue에 있으면, 반복문을 중지하고 카운트한 값을 출력해준다.

 

from collections import deque

def walk_b(loc):
    return (loc - 1)

def walk_f(loc):
    return (loc + 1)

def teleport (loc):
    return (2 * loc)

N, K = map(int, input().split())
queue = deque()
cnt = 0
check = [False] * 100001

queue.append(N)

def bfs():
    for _ in range(len(queue)):
        x = queue.popleft()
        y1 = walk_b(x)
        y2 = walk_f(x)
        y3 = teleport(x)
        if 0 <= y1 and check[y1] == False and 0 <= y1 <= 100000:
            check[y1] = True
            queue.append(y1)
        if 0 <= y2 and x < K and check[y2] == False and 0 <= y2 <= 100000:
            check[y2] = True
            queue.append(y2)
        if x < K and 0 <= y3 <= 100000:
            check[y3] = True
            queue.append(y3)

while K not in queue:
    bfs()
    cnt += 1
print(cnt)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.