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

 

 

문제 링크: https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

 

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

    n, k = map(int, input().split())    #n는 수빈, k는 동생
    max = 100000                        #n,k <= 100000이기 때문에 최댓값을 잡아줍니다.
    length = [0 for _ in range(max+1)]  #최대값 내의 숫자만큼(100001개) length 배열을 생성

    def bfs():
        q = deque()                     # queue보다는 deque를 사용합시다.
        q.append(n)
        while q:                        #q에 체크할 위치가 남아있다면
            temp = q.popleft()
            if temp == k:
                print(length[temp])
                break
            for j in (temp-1, temp+1, temp*2):
                if 0 <= j <= max and not length[j]: # and문에서 범위 체크 먼저하는게 매우중요!!
                    length[j] = length[temp] + 1
                    q.append(j)

    bfs()

BFS(breadth-first search) 문제네요.

수빈이가 서있는곳에서 -1, +1, x2인 위치들을 deque에 넣고 확인해 나가면 됩니다.
deque를 쓰는 이유는 queue 보다 효율적이여서겠죠?
deque가 생소하신 분들은 이 링크(https://ooeunz.tistory.com/31)를 참조하거나 따로 검색을 하셔서 공부를 해보시는 것을 추천합니다. popleft()를 사용할 수 있는 것이 queue와의 차이라고 할 수 있어요.

쉬운 문제지만 자유자재로 풀어나갈 때까지 계속 포스팅할게요. 피드백 감사합니다.