[알고리즘] BOJ 1697번 - 숨바꼭질(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

3 / 50

 

탐색

4 / 50(NEW!)

 

기초 동적 프로그래밍

3 / 50

 

투포인터

0 / 10

 

---

문제

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

→ solved.ac 기준 실버 1

---

문제 해결 아이디어

걷는다면, x - 1 또는 x + 1로 이동

순간이동하면, 2 * x의 위치로 이동

동생을 찾을 수 있는 가장 빠른 시간?

 

단순하게 이동하면서 최단 경로를 찾는다고 하면

순간이동했을 때와 걸었을 때 y보다 덜 차이가 나는 걸로 하면 되지 않을까?

→ 근데 n와 k의 최대값이 100,000.. 단순하게 실험해봤는데도 엄청 오래 걸림

예제 입력을 확인했을 때도 늘 차이가 적게 나는 걸로 가지 않음(ex. 10에서 9로 갔을 때)

 

알고리즘 분류가 BFS로 되어있으므로 일단 그 방식으로 생각해보면

각 X는 X - 1과 X + 1, 2 * X로 연결되어있으며,

Y로 가는 최단 경로를 구하는 게 요지가 아닐까? 하고 유추

---

구현

내 풀이

import sys
from collections import deque

input = sys.stdin.readline

MAX = 100001

# BFS 소스 코드 구현
def bfs(x):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append(x)
    
    # 큐가 빌 때까지 반복하기
    while queue:
        x = queue.popleft()

        for i in range(3):
            if i < 2:
                nx = x + dx[i]
            else:
                nx = 2 * x

            if nx < 0 or nx >= MAX:
                continue
            
            if graph[nx] == 1:
                graph[nx] = graph[x] + 1
                queue.append(nx)

    # k까지의 최단 거리 반환
    return graph[k] - 1

x, k = map(int, input().split())
graph = [1] * MAX
dx = [-1, 1]
if (x == k):
  print(0)
else:
  print(bfs(x))

---

메모

• 걸린 시간: 1시간
• 정답에 비해 제출이 많다 싶었는데.. 초반 시도가 많았음..
  • 첫 번째는 인덱스. 100001로 MAX 값을 설정해주어야 했다.
  • 두 번째는 x와 k가 같을 때에도 생각해주어야 함

---

마치며

BFS랑 DFS 문제인 줄 몰랐으면 못 풀었을 듯.

BFS 문제라는 걸 보고나서는 시간 거의 안 걸리고 풀었다..

역시 많이 푸는 게 답인가보다.