[백준12851] / 숨바꼭질 2 - BFS

 

백준12851

 

푼 날짜 : 2024.10.11

푼 문제 : [12851] / 숨바꼭질 2

사용한 언어 : python

알고리즘 : BFS

 

 

접근 방식 :

 

사실 저번에 풀다가 "가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성" 에서 막혔었다.

1 2
1 + 1 => 2
1 * 2 => 2

 

요런 테케의 경우 방법이 2가지인데 방문 처리를 해버리는 순간 조건문 안에 안들어가서 고민을 좀 했다.

 

visited[i] == -1 or visited[i] == visited[now] + 1

 

디버깅 하다가 요렇게 수정하고 바로 통과 !

역시 오늘도 하나 배워갑니다..

 

 

 

코드 :

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
visited = [-1 for _ in range(100001)]

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

    ans = 0
    while queue:
        now = queue.popleft()

        lst = [now+1, now-1, now*2]
        for i in lst:
        	# 범위 안에 있고, 방문하지 않았거나, 방문한 곳인데 최단 거리 일 경우
            if 0<=i<100001 and (visited[i] == -1 or visited[i] == visited[now]+1):
                if i == K: ans += 1 # 일치할 경우 카운트
                queue.append(i)
                visited[i] = visited[now] + 1 
   
    print(visited[K])    
    print(ans)  

# 처음부터 같은 위치에 있었을 경우
if N == K:
    print(0)
    print(1)
else: 
    BFS(N)

 

 

 

그래프 문제는 정말 흥미로워라~