백준 #13549: 숨바꼭질3/ 골드5 / 그래프

문제 링크 : https://www.acmicpc.net/problem/13549

🔍 Inspection

문제 접근(문제 분석 → 풀이 아이디어)

[1] BFS 로 풀기 (0-1 BFS)

[2] 다익스트라 사용하기

🚩 FLOW

코드를 풀이할 때 적었던 플로우가 있나요?

1. 입력 변수 입력하기

   1. visited[현 위치] = 도달하는데 걸리는 시간 ( default = MAX)
   2. deque 인 q : 위치 x

2. BFS 탐색 시 순간이동을 우선순위를 둠

   → for문 탐색시 , 2*n >> n-1, n+1 순으로 탐색

3. 배열 visited에 도착 시간 업로드

   1. 순간이동 한 경우 → +0초
   2. 걸어온 경우 → +1 초

🚩제출한 코드

import sys
from collections import deque
input = sys.stdin.readline
MAX = 100001
N , K  = map(int,  input().split())
visited = [MAX] * (MAX+1) 

# 2. BFS로 탐색하기
q = deque([N])
visited[N]= 0 

while q : 
  cx= q.popleft()
  ct = visited[cx] 
  if cx == K: 
     break
  for nx in (2*cx , cx-1 , cx+1 ) : # 순간이동 >> 걷기 순의 탐색 우선순위 두기
    if 0 <= nx < MAX and visited[nx] >= MAX : # nx 의 제한 조건
      # 시간 업데이트 
      if nx == 2*cx : 
          visited[nx] = visited[cx]
      else : 
          visited[nx] = visited[cx] +1
      q.append(nx)
print(visited[K])

• 💥 1차 제출