[백준] 1697 숨바꼭질 (실버1) / BFS

문제요약

나의 코드 및 설명

• 문제의 조건 범위(0이상 100000이하)에 해당하는 룩업테이블 visited 리스트를 만들고, 방문 할 때마다 visited 리스트에 저장된 값을 1씩 증가시킨다. 
• 만약 동생을 만나게 된다면, 현재까지의 visited 리스트에 저장된 값에서 1을 빼준 값을 리턴한다.

from collections import deque

def bfs(sx, ex):
    global count
    queue = deque()
    queue.append(sx)
    #수빈이 위치 방문처리 
    visited[sx] = 1

    while queue:
        x = queue.popleft()
        if x == ex: #수빈이가 동생과 만난다면 
            return visited[x] - 1 #룩업테이블에 저장된 값-1 리턴
        for i in (x-1, x+1, 2*x): #수빈이가 갈 수 있는 위치
            #문제의 조건 범위를 벗어나지 않고, 방문하지 않은 곳이라면
            if 0<=i<=100000 and visited[i] == 0:
                #우선 방문처리
                visited[i] = visited[x] + 1
                #큐에 다음 좌표 삽입
                queue.append(i)
                
n, k = map(int, input().split())
visited = [0] * 100001 #룩업테이블(문제의 조건 범위)
count = 0

print(bfs(n,k))

피드백

이전까지는 이차원 리스트에서 최단 거리를 찾는 데에 BFS를 활용했었는데, 이번엔 일직선에서 최단거리를 찾는 문제라 처음 풀 때는 되게 어려웠던 것 같다. 특히, 수빈이가 움직일 수 있는 좌표가 x-1, x+1, 2*x 셋 중 하나인데, 이를 어떻게 표현해야 할지도 막막했던 문제. 

다른 사람의 풀이를 참고하고 '아, 이거구나' 싶었다. for i in (x-1, x+1, 2*x) 로 간단하게 표현할 수 있었던 것이다.

또한 문제의 조건 범위를 직접적으로 코드에 활용한 문제가 많지 않았는데, 이번 기회로 문제의 조건 범위를 코드에 활용하는 데에 조금 더 익숙해줄 수 있었던, 배울 점이 많았던 문제였다.