백준 1697

ALGORITHM
2025-09-05

숨바꼭질

관련 개념

#BFS

문제

백준 1697

📌 1 단계 : 문제 분석하기

  • 처음에 문제를 봤을 때, 그리디, DP 등 여러 방법을 떠올렸지만, 마땅한 방법이 없어서 브루트포스로 풀 되, 최대한 넣는 경우의 수를 줄이자고 생각했다.
  • 브루트포스의 구현 중 하나는 너비 우선 탐색이다.

📌 2 단계 : 손으로 풀어보기

  1. 수빈이가 움직일 수 있는 좌표들을 큐에 넣는다
  2. 해당 큐에서 이미 도달한 정점을 제외한다.
  3. 이를 최초로 도달 할 때까지 반복한다.

📌 3 단계 : 슈도 코드 작성하기

  • 생략

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm>
#include <set>
 
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int N, K;
	int ans = INT_MAX;
 
	cin >> N >> K;
 
	queue<pair<int, int>> q;
	vector<bool> visited(200001, false);
 
	// 시작점
	q.push({ N , 0 });
	visited[N] = true;
 
	while (!q.empty()) {
		int location = q.front().first;
		int time = q.front().second;
		q.pop();
 
		// 해당 위치에 도달했다면 체크
		if (location == K) {
			ans = time;
			break;
		}
 
		else {
			// 조건 1. 해당 지점이 방문되지 않았다면
			if (location >= 1 && !visited[location - 1]) {
				q.push({ location - 1, time + 1 });
				visited[location - 1] = true;
			}
 
			if (location < K  && !visited[location + 1]) {
				q.push({ location + 1, time + 1 });
				visited[location + 1] = true;
			}
 
			if (location < K && !visited[2 * location]) {
				q.push({ 2 * location, time + 1 });
				visited[2 * location] = true;
			}
 
		}
	}
 
	cout << ans;
 
}

📌 5 단계 : 배운점

  • BFS의 특성을 망각했다.
  • BFS의 특성 상, 가장 가까운 거리부터 탐색을 하게 된다. 이 말은 즉, 특정 index에 도달했다면, 경로가 최소 시간이라는 뜻이다.
    • BFS 특성 주의!!
  • 따라서, 최초로 해당 K에 도달한 시간이 최소 시간이다.
  • 또, 메모리 초과 문제가 발생했는데, K는 작지만, N이 굉장히 큰 경우의 수를 고려하지 못했다…
  • 경계값에 주의하자!!