[백준] 1697 숨바꼭질 (Python)

문제 링크

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

1697번: 숨바꼭질

나의 풀이

• 최단거리를 구하기 위해 bfs를 사용했습니다.
• 최대 입력이 100,000까지라 maps를 100,001 크기로 설정했습니다.
• bfs알고리즘을 수행하며 x+1, x-1, x*2로 탐색을 했습니다.
  
  • 인덱스 에러 방지 및 방문한 지점에 대해서 예외처리를 진행합니다.
• deque.leftpop()에서 목표 지점과 동일한 값이 나오면 bfs()를 종료합니다.

Code

from collections import deque


def bfs():
    q = deque()
    q.append(start)

    while q:
        x = q.popleft()
        if x == end:
            print(maps[x])
            break

        for nx in (x + 1, x - 1, x * 2):
            if 0 <= nx < 100001 and maps[nx] == 0:
                maps[nx] = maps[x] + 1
                q.append(nx)


start, end = map(int, input().split())
maps = [0] * 100001
bfs()

Git

https://github.com/youngh0/Algorithm/blob/master/DFS%2CBFS/boj_1697_BFS.py