코딩 테스트 연습/백준

[Python]Baekjoon 1697번: 숨바꼭질

jaeheon0520 2024. 3. 5. 20:04

1. 문제

 

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

 

1697번: 숨바꼭질

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

www.acmicpc.net

 

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

 

시작 지점에서 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중 어떤 알고리즘이 더 효율적일지 생각해 볼 수 있었다.

 

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

 

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

 

오늘 하루도 쌓였다.