[백준1697] / 숨바꼭질 - 그래프(BFS)

 

백준1697

 

 

푼 날짜 : 2024.08.17

푼 문제 : [1697] / 숨바꼭질

사용한 언어 : python

 

 

푼 방법 :

너비 우선 탐색으로 접근하였다.

 

이동 가능한 범위는 현재위치에 +1, -1, *2 였기 때문에 이를 배열로 만들어 반복문을 돌며 확인하도록 했다.

나머지 방식은 일반적인 BFS와 동일하다.

 

 

코드 :

import sys
from collections import deque

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

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

    while queue:
        now = queue.popleft()
        nx = now
        if nx == K: break
        for i in range(3):
            if px[i] == '-': nx = now - 1
            elif px[i] == '+': nx = now + 1
            elif px[i] == '*': nx = now * 2
            if 0<=nx<100001:
                if visited[nx] == -1:
                    queue.append(nx)
                    visited[nx] = visited[now] + 1
                    
            
graph_ = [0 for _ in range(100001)]
visited = [-1 for _ in range(100001)]

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

 

 

 

정답률이 낮아 어려울 것 같다고 생각했으나 실상 접근해보니 그렇게까지 어려운 문제는 아니었다!

오늘도 자신감 UP !