minyeamer
Minystory
minyeamer
edit settings
전체 방문자
오늘
어제
  • Category List (104)
    • Books (5)
      • Book Reviews (1)
      • Paper Reviews (4)
    • Life (4)
      • Blog (3)
      • Item Reviews (0)
      • Thoughts (1)
    • Study (37)
      • 2022 (3)
      • AI SCHOOL (34)
      • References (0)
    • Tech (58)
      • Algorithm (47)
      • Projects (9)
      • Python (2)

Blog Menu

  • Home
  • Notice
  • Tags
  • Guest

Popular Posts

Recent Comments

Recent Posts

hELLO
minyeamer
Tech/Algorithm

[백준 1697] 숨바꼭질 (Python)

Tech/Algorithm

[백준 1697] 숨바꼭질 (Python)

2022. 8. 16. 18:53

문제 링크

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

문제 해설

Idea

  • BFS
  • N에서 시작해 K에 도달할 때까지 x-1, x+1, x*2에 대한 최단거리를 탐색
  • 두 점이 위치할 수 있는 범위 내에서 가까운 거리의 점부터 탐색을 수행하고 K에 대한 거리를 출력
  • N이 K보다 클 경우 x-1 외에는 이동수단이 없기 때문에 시간 단축을 위해 예외로 처리

Time Complexity

  • O(N) = 100,000

Data Size

  • N: 0 <= int <= 100,000
  • K: 0 <= int <= 100,000

해설 코드

from collections import deque

def bfs(start, target):
    MAX = 10**5
    count = [0] * (MAX+1)
    queue = deque([start])

    while queue:
        x = queue.popleft()
        if x == target:
            return count[x]
        for nx in (x-1,x+1,x*2):
            if 0 <= nx <= MAX and not count[nx]:
                count[nx] = count[x] + 1
                queue.append(nx)

N, K = map(int, input().split())

if N >= K:
    print(N - K)
else:
    print(bfs(N, K))
저작자표시 (새창열림)

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

[프로그래머스]n^2 배열 자르기 (Python)  (0) 2022.08.16
[프로그래머스]n진수 게임 (Python)  (0) 2022.08.16
[백준 1676] 팩토리얼 0의 개수 (Python)  (0) 2022.08.16
[백준 1541] 잃어버린 괄호 (Python)  (0) 2022.08.16
[백준 1389] 케빈 베이컨의 6단계 법칙 (Python)  (0) 2022.08.16
  • 문제 링크
  • 문제 해설
  • 해설 코드
'Tech/Algorithm' 카테고리의 다른 글
  • [프로그래머스]n^2 배열 자르기 (Python)
  • [프로그래머스]n진수 게임 (Python)
  • [백준 1676] 팩토리얼 0의 개수 (Python)
  • [백준 1541] 잃어버린 괄호 (Python)
minyeamer
minyeamer
Better than Yesterday

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.