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

2023. 9. 10. 00:40·Algorithm/BaekJoon
import sys
from collections import deque

input = sys.stdin.readline
MAX = 100000 + 1

n, k = map(int, input().split())
visited = [-1] * MAX  # [위치][시간] 으로 하려고 했으나 메모리 초과로 [위치]=시간으로 바꿈(물론 dist 배열을 따로 둬도 됨)

def bfs():
    q = deque()
    q.append(n)
    visited[n] = 0

    while q:
        loc = q.popleft()

        # 동생 위치를 찾음
        if loc == k:
            return visited[loc]

        # 순간이동
        if loc * 2 < MAX and visited[loc*2] == -1:
            visited[loc*2] = visited[loc]
            q.appendleft(loc*2) # 2*s가 다른 연산보다 더 높은 우선순위를 가지기 위함(순간이동이 최단시간 도출에 핵심이라 먼저 해야 값이 저장됨)

        # 걷기
        for dx in [-1, 1]:
            nx = loc + dx
            if 0 <= nx < MAX and visited[nx] == -1:
                visited[nx] = visited[loc] + 1
                q.append(nx)


print(bfs())

'Algorithm > BaekJoon' 카테고리의 다른 글

[백준/Python] 2748번 - 피보나치 수 2  (0) 2023.09.29
[백준/Python] 1600번 - 말이 되고픈 원숭이  (0) 2023.09.10
[백준/Python] 3184번 - 양  (0) 2023.09.09
[백준/Python] 9375번 - 패션왕 신해빈  (0) 2023.09.09
[백준/Python] 2146번 - 다리 만들기  (0) 2023.09.06
'Algorithm/BaekJoon' 카테고리의 다른 글
  • [백준/Python] 2748번 - 피보나치 수 2
  • [백준/Python] 1600번 - 말이 되고픈 원숭이
  • [백준/Python] 3184번 - 양
  • [백준/Python] 9375번 - 패션왕 신해빈
빵빵0
빵빵0
(아직은) 공부하고 정리하는 블로그입니다.
  • 빵빵0
    Hack Your World
    빵빵0
  • 전체
    오늘
    어제
    • 분류 전체보기 (94)
      • Error Handling (7)
      • Project (5)
        • MEV (2)
      • Architecture (0)
        • API (0)
        • Cache (0)
        • 사소한 고민거리 (0)
      • Computer Science (4)
        • Data Structure (2)
        • Database (1)
        • Cloud (0)
        • OS (0)
        • Infra, Network (1)
        • AI (0)
      • Language (10)
        • Go (10)
        • Rust (0)
        • Python (0)
        • Java (0)
      • Algorithm (40)
        • BaekJoon (18)
        • Programmers (7)
        • LeetCode (6)
        • NeetCode (9)
      • SW Books (9)
        • gRPC Up & Running (1)
        • System Design Interview (2)
        • 스프링 입문을 위한 자바 객체지향의 원리와 이해 (6)
        • 블록체인 해설서 (0)
        • 후니의 쉽게 쓴 CISCO 네트워킹 (0)
      • BlockChain (4)
        • Issues (0)
        • Research (4)
        • Tech (0)
      • Own (8)
        • TIR(Today I Read) (3)
        • Personal (2)
        • Novel (0)
        • Memo (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Palindrome
    Python
    스택
    golang
    two pointer
    ethereum
    MEV
    Programmers
    Hash Table
    context
    BaekJoon
    goroutine
    go
    blockchain
    Greedy
    2024
    MongoDB
    BFS
    큐
    KBW
    NeetCode
    백준
    BEAKJOON
    블록체인
    LeetCode
    DP
    프로그래머스
    candlechart
    chart
    EVM
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
빵빵0
[백준/Python] 13549번-숨바꼭질 3
상단으로

티스토리툴바