[백준] 1697번 - 숨바꼭질 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

이 문제는 시작 위치와 목표 위치를 입력 받아 이동하는 최소한의 횟수를 구하는 문제이다.

한 정점 x에서 이동 가능한 지점을 미리 정의하고 BFS를 이용했다.

 

이동 가능한 위치의 정점이 범위를 벗어나거나, 이미 방문한 정점인 경우는 무시하고

방문이 가능할 경우에는 현재 정점의 값에서 1을 더하면서 이동한다.

 

한 번 이동할때마다 값을 증가시켜서 최종 필요 시간을 알 수 있게한다.

만약 BFS를 진행하는 도중에 목표 위치를 만나면 더 이상 진행하지 않고 종료한다.

가장 먼저 목표 위치에 도달했을 때의 카운트가 최소 카운트일 것이기 때문이다.

 

[소스코드]

from collections import deque

n, k = map(int, input().split())

visited = [0] * 100001
dx = [1, -1, 2]

def bfs(cur, target):
    queue = deque()
    queue.append(cur)
    visited[cur] = 0

    while queue:
        x = queue.popleft()
        if x == target:
            print(visited[x])
            return 0
        for i in range(3):
            if i == 2:
                nx = x * dx[i]
            else:
                nx = x + dx[i]
            if nx < 0 or nx > 100000:
                continue
            if visited[nx] > 0:
                continue
            visited[nx] = visited[x] + 1
            if nx == target:
                print(visited[nx])
                return 0
            queue.append(nx)


bfs(n, k)

처음에 실수했던 부분이 방문을 체크하는 리스트 visited를 선언하는 부분이었다.

시작 위치와 목표 위치 모두 0 ~ 100,000이 될 수 있으므로 1이 더 큰 100,001 이 리스트의 크기가 되어야했지만 100,000로 크기를 정해서 런타임 오류가 발생했었다.