[백준(BOJ)] 13549번 : 숨바꼭질 3 - PYTHON[파이썬]

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 다익스트라
• 0-1 너비 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

방문 여부를 카운트로 하여 방문 시에 +1을 count up 해주었다.

만약 순간이동 하는 경우는 방문 카운트를 건드리지 않는다.

왜냐하면 순간이동에 걸리는 시간은 0초이기 때문이다.

그리고 순간이동의 경우에는 left로 가장 맨 앞으로 넘겨준다.

 

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
q = deque()
q.append(N)
visited = [-1 for _ in range(100001)]
visited[N]=0

while q:
    s=q.popleft()
    if s == K:
        print(visited[s])
        break
    if 0 <= s-1 < 100001 and visited[s-1]==-1:
        visited[s-1]=visited[s]+1
        q.append(s-1)
    if 0 <= s*2 < 100001 and visited[s*2]==-1:
        visited[s*2]=visited[s]
        q.appendleft(s*2)
    if 0 <= s+1 < 100001 and visited[s+1]==-1:
        visited[s+1]=visited[s]+1
        q.append(s+1)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!