[백준13549] / 숨바꼭질3 - BFS

 

백준13549

 

푼 날짜 : 2024.09.06

푼 문제 : [13549] / 숨바꼭질3

사용한 언어 : python

 

 

푼 방법 :

BFS로 접근했다.

여기서 이전 문제들과 달랐던 점은 다른 이동은 1초 후 이동, 순간이동을 하는 것은 0초 라는 것!

 

따라서 계산 순서를 [순간이동(*2칸), -1칸, +1칸] 으로 두고 코드를 작성하였는데
지금 생각해보니 순간이동 가능한 범위(max는 동생의 위치 *2 정도로 잡으면 될 것 같다.)를 먼저 다 계산하고 추후 계산(+1, -1)을 해도 될 것 같다는 생각이 들었다.

 

 

 

코드 :

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
dx = ['*', '-', '+']

def BFS(visited, v):
    queue = deque([v])
    visited[v] = 0

    while queue:
        now = queue.popleft()
        if now == K: break

        for i in dx:
            check = False
            nx = now
            if i == '*': 
                check = True 
                nx = now * 2
            elif i == '-': nx = now - 1
            elif i == '+': nx = now + 1   
            
            if 0<=nx<=100000 and visited[nx] == -1:
                queue.append(nx)
                if check: visited[nx] = visited[now]
                else: visited[nx] = visited[now] + 1


visited = [-1 for _ in range(100001)]

BFS(visited, N)
print(visited[K])

 

 

 

오랜만에 그래프 문제를 풀다보니 조건과 범위를 깊게 생각하지 못하고

if 0<=nx<=100000 and visited[nx] == -1:

 

해당 코드를 

 

if visited[nx] == -1 and 0<=nx<=100000:

 

로 작성하며 런타임에러(IndexError)가 발생했었다.

 

 

로직은 두고 배열에 접근하기 전 범위를 먼저 확인하도록 수정하여 제출했다.

생각하면서 로직을 짜자!!!!!