[백준 BOJ] 1697번 숨바꼭질 (C++/cpp)

문제 설명

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

1697번: 숨바꼭질

 

접근 방법 - 그래프 탐색의 심화문제 (BFS)

백준의 1697번 문제는 그래프 탐색에 있어 다소 심화적인 부분을 다루고 있는 문제이다.

해당 문제는, 수빈이와 동생의 위치가 주어지고 수빈이가 특정 규칙대로 움직일 수 있을 때 수빈이 동생을 찾는 데에 몇 초가 걸리는지를 출력해야 하는 문제이다.

이 문제와 같은 경우엔, BFS를 어느 정도 구현할 수 있다면 어렵지 않게 해결할 수 있는 문제이다.

다만, 수빈이 이동할 수 있는 규칙에 대하여 주어진 범위를 벗어나서는 안 된다는 점을 고려하면서 코딩을 진행해야 한다.

그리고 동생을 찾는 방법의 가짓수가 여러 가지가 나올 수도 있기 때문에, 꼭 최솟값만을 도출하여 출력해야 한다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 수빈이 이미 방문한 지점인지에 대한 여부를 저장할 배열(visit)을 전역 변수로 선언해 둔다.

(필자는 범위를 여유롭게 두기 위해 아래와 같이 하였지만, 총범위가 10만이라는 것만 고려하여 설정하면 된다.)

 

2) 수빈이와 동생의 위치(a, b)를 순차적으로 입력받는다.

 

3) BFS 연산을 수행하기 위한 큐(q)를 <int, int> 형태로 선언한다.

(이때, <수빈의 현재 위치, 현재까지 걸린 시간> 순으로 큐에 저장할 예정이다.)

 

4) q를 선언하는 대로, q에 <a, 0> 형태의 정보를 push한다.

 

5) 최소 시간을 저장할 변수 min을 임의의 큰 수로 초기화하며 선언한다.

(가장 작은 값을 저장하기 위해 존재하는 변수이기 때문에, 임의의 큰 수로 우선 저장해 둔 뒤 차후에 잇따라 갱신하도록 한다.)

 

6) q가 빌 때까지, 반복문을 통해 아래의 연산을 수행한다.

- q의 front 값에 대하여, 첫 번째 값인 현재 위치(re)와 두 번째 값인 걸린 시간(cnt)을 임의의 각 변수에 저장해 둔다.

(만약 re의 값이 동생의 위치인 b와 같고 현재의 min 값보다 cnt가 더 작다면, min의 값을 현재 cnt의 값으로 갱신한다.)

- 만약 cnt+1의 값이 min보다 작다면, 이는 현재로선 최소 시간의 경로가 더 존재할 수 있다는 점을 의미한다. 따라서, 아래처럼 하자.

수빈이 움직일 수 있는 패턴은, re+1 / re-1 / re*2 이렇게 3가지이다.
만일 각 경우에 대하여, 아직 방문하지 않은 위치이며 해당 위치가 범위 안의 위치라면 수빈은 해당 위치를 방문해 볼 수 있다.
따라서 이 경우엔, <해당 위치, cnt+1> 형태의 정보를 q에 push하고 해당 위치에 대한 visit의 값에 1을 추가하여 방문했음을 표시한다.
(이때, 해당 위치로 이동할 때 시간이 1초 추가로 소요되기 때문에 second의 값을 cnt+1로 설정하여 저장하게끔 하였다.)

- 위 연산이 완료되었다면, q에 대하여 pop 연산을 취한다.

 

7) BFS 연산이 모두 완료되었다면, 최종적으로 저장된 min의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <queue>
#include <utility>
#define endl '\n'
using namespace std;

//백준 1697번 코드
int visit[200001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int a, b;
	cin >> a >> b;

	queue<pair<int, int>> q;
	q.push(make_pair(a, 0));
	int min = 100000;
	while (!q.empty()) {
		int re = q.front().first;
		int cnt = q.front().second;
		if (re == b && cnt < min) { min = cnt; }
		if (cnt + 1 < min) {
			if (re + 1 <= 100000 && re + 1 >= 0 && visit[re + 1] == 0) {
				q.push(make_pair(re + 1, cnt + 1));
				visit[re + 1]++;
			}
			if (re - 1 <= 100000 && re - 1 >= 0 && visit[re - 1] == 0) {
				q.push(make_pair(re - 1, cnt + 1));
				visit[re - 1]++;
			}
			if (re * 2 <= 100000 && re * 2 >= 0 && visit[re * 2] == 0) {
				q.push(make_pair(re * 2, cnt + 1));
				visit[re * 2]++;
			}
		}
		q.pop();
	}

	cout << min << endl;
}

 

제출 결과

왜 이렇게 틀렸나 했더니, 값 확인 출력 때문이었다 카더라

(2022.08.30 백준 1697번 문제 제출 결과)