hgk0404.tistory
Code After Work
hgk0404.tistory

공지사항

전체 방문자
오늘
어제
  • 전체 카테고리
    • [컴퓨터비전]
    • [Computer Science]
      • [컴퓨터네트워크]
      • [알고리즘]
      • [자료구조 in C]
      • [C & C++]
      • [이산수학]
      • [Math]
    • [머신러닝]
      • [Numpy, Pandas]
    • [Cloud]
      • [AWS]
      • [NCP]
      • [Kubernetes]
      • [Terraform]
    • [Dev]
      • [가상환경]
      • [Linux]
      • [Docker]
    • [Python]
    • [Coding Test]
      • [백준]
      • [프로그래머스]
      • [SQL]
    • [WEB]
    • [일상]
    • [엑셀]
    • [금융]

인기 글

최근 글

최근 댓글

250x250
hELLO · Designed By 정상우.
hgk0404.tistory

Code After Work

[백준] 1697: 숨바꼭질
[Coding Test]/[백준]

[백준] 1697: 숨바꼭질

2022. 6. 30. 22:46
728x90

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

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있습니다.

import sys
from collections import deque
def solution():
    n, k = map(int, sys.stdin.readline().split())
    def bfs():
        visited = [0]*100001
        q = deque()
        q.append(n)
        while q:
            now = q.popleft()
            if now == k:
                return visited[now]
            for next in (now-1, now+1, 2*now):
                if 0 <= next < 100001 and not visited[next]:
                    visited[next] = visited[now] + 1
                    q.append(next)
    print(bfs())
solution()

출발 지점의 visited는 따로 처리해주지 않고 0으로 두어도 괜찮습니다.

왜냐하면 n == k인 경우(수진이와 동생의 위치가 같은 경우)는 bfs()를 실행하자마자 now == k에 걸리게 되어 0초를 반환하게 되고 나머지의 경우는모두 1초 이상이 걸리기 때문에 visited[next] = visited[now] + 1을 해주면서 최단 거리를 구하게 됩니다.

728x90
저작자표시 동일조건 (새창열림)

'[Coding Test] > [백준]' 카테고리의 다른 글

[백준] 1181: 단어 정렬  (0) 2022.07.03
[백준] 1157: 단어 공부  (0) 2022.07.02
[백준] 7569: 토마토  (0) 2022.06.30
[백준] 2667: 단지번호붙이기  (0) 2022.06.29
[백준] 1182: 부분수열의 합  (0) 2022.06.28
'[Coding Test]/[백준]' 카테고리의 다른 글
  • [백준] 1181: 단어 정렬
  • [백준] 1157: 단어 공부
  • [백준] 7569: 토마토
  • [백준] 2667: 단지번호붙이기
hgk0404.tistory
hgk0404.tistory
공부기록

티스토리툴바