백준 - 숨바꼭질(1697)

정민주·2025년 1월 20일

코테

목록 보기

43/95

오늘 풀어볼 문제는 ⭐숨바꼭질 이란 문제이다.

일단 틀렸다. 해당 문제는 bfs로 풀어야 효율적인 문제였는데, 난 dfs를 이용해서 계속 도전하다가 실패했었다. 오늘 포스팅은 해당 문제는 왜 dfs가 아닌 bfs로 풀어야 하는가에 대한 것이다.

✅1. 문제 설명

입력으로 나의 위치와 동생의 위치가 주어진다. 둘은 일직선 상에 위치한다.
현재 내 위치에서 +1, -1, *2 만큼 움직일 수 있다.
동생에게 도달하기 위한 최소의 움직임 횟수를 구하여라.

✅2. BFS VS DFS

BFS나 DFS같은 알고리즘을 그래프 탐색 알고리즘이라고 한다.

그래프 탐색 알고리즘?

그래프란 여러 개체들이 연결되어 있는 자료구조라고 할 수 있다. 그래프 탐색 알고리즘이란 이 여러개체들 중 특정 개체를 찾기 위한 알고리즘이다.

BFS의 최대 장점은 현재 위치에서 갈 수 있는 모든 위치를 한 번에 갈 수 있다는 것이다.

DFS의 경우에는 재귀함수로 구현되기에 우리가 갈 수 있는 3가지의 경로 중, 하나만을 끝까지 가본 후 다시 돌아오는 것이 특징이다. 이렇게 하면 3가지 경로 중 항상 최선의 경로로만 움직이지는 않기 때문에, 해당 3가지 경로를 모두 dfs로 탐색을 해봐야 한다는 의미이다.

이렇게 되면 해당 문제의 시간 복잡도는 3^100,000 까지 늘어나게 되므로 당연히 시간 초과가 발생한다.

이런 경우 우리는 bfs를 이용해 풀 수 있다.

✅3. 문제 풀이

문제에서 주어진 예시를 한번 보겠다. 수빈이의 위치는 5이고 동생의 위치는 17이다. 따라서 0초에 있는 곳은 표시를 해두겠다.

1초 때는 X-1, X+1, 그리고 2X로 이동할 수 있어서 4, 6, 그리고 10으로 이동할 수 있다. 표로 표현하면 다음과 같다.
1초에 4, 6, 그리고 10으로 이동한 것을 볼 수 있다.

이미 간 곳을 제외하고 그 다음에는 2초에는

위치 4에서 3, 8로 갈 수 있다.
위치 6에서 7, 12로 갈 수 있다.
위치 10에서 9, 11, 20으로 갈 수 있다.

그 다음 3초에는

3에서 2로 갈 수 있다.
7에서 14로 갈 수 있다.
8에서 16으로 갈 수 있다.
9에서 18로 갈 수 있다.
11에서 22로 갈 수 있는데 20 이상은 편의를 위해서 제외시키겠다.
12에서는 13, 24로 갈 수 있다.
20에서 19, 21, 40으로 갈 수 있다.