[Python]Baekjoon 1697번: 숨바꼭질

1. 문제

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

1697번: 숨바꼭질

시작 지점과 도착 지점을 입력받는다.

시작 지점에서 x+1, x-1, x*2 세 가지 방법을 활용해서 최대한 빨리 도착 지점으로 가는 문제이다.

최대한 빨리 갔을 때 몇 번 이동했는지 출력하면 된다.

2. 풀이

최단 시간 길 찾기 문제이므로 BFS를 활용할 것이다.

BFS 함수에서 시작하는 좌표를 전달받고 큐에 넣어준다.

일반적인 길찾기 문제와 달리 이 문제는 갈 수 있는 방향이 앞, 뒤, *2 총 3가지이다. 즉 노드가 3방향으로 뻗을 수 있다.

반복문을 이용하여 v-1, v+1, v*2가 담겨있는 배열을 순회한다.

좌표에 해당하는 배열에 몇 번째로 이동한 건지(몇 초 걸렸는지) 저장하고

각 좌표를 순회하면서 큐에 좌표를 추가한다.

한번 방문한 노드는 다시 방문하지 않기 위해 and not array[next_v] 부분을 추가해 주었다.

이 부분이 없으면 메모리 초과가 발생한다.

이전에 고려한 노드를 또 큐에 넣어서 두 번 고려할 필요는 없다.

3. 코드

from collections import deque

import sys

input = sys.stdin.readline

MAX = 100001

array = [0] * MAX

start, end = map(int, input().split())

def bfs(v):

queue = deque([v])

while queue:

v = queue.popleft()

if v == end:

return array[v]

for next_v in (v-1, v+1, 2*v):

if 0 <= next_v < MAX and not array[next_v]:

array[next_v] = array[v] + 1

queue.append(next_v)

print(bfs(start))

4. 느낀점

상하좌우로 이동하는 일반적인 그래프 문제와는 조금 다른 문제였다.

DFS와 BFS중 어떤 알고리즘이 더 효율적일지 생각해 볼 수 있었다.

문제마다 더 효율적인 알고리즘을 생각해 볼 필요가 있음을 알게 되었고,

메모리 초과와 관련된 부분도 생각해 볼 수 있었다.(방문했던 노드 다시 방문하지 않기)

오늘 하루도 쌓였다.