[G5] 백준 12852번 1로 만들기 2 C++ 너비 우선 탐색

리뷰

 

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

지정한 수를 주어진 연산을 통해 1로 만드는 시간과 그 경로를 출력하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• x : 시작 정수를 저장할 변수
• v : 도달한 시간을 저장할 배열
• path : 현재 정수에 도달하기 전의 이전 정수값을 저장할 배열
• q : 탐색중인 정수를 저장할 큐

 

함수

1. insert

void insert(int cx, int nx) {
	if (1 <= nx && nx < N && !v[nx]) {
		v[nx] = v[cx] + 1;
		path[nx] = cx;
		q.push(nx);
	}
}

 

수에 도달 가능하지 여부를 체크하고 이동을 수행하는 함수

 

2. bfs

void bfs() {
	q.push(x);

	while (!q.empty()) {
		int cx = q.front(); q.pop();
		if (cx == 1) break;

		if (cx % 3 == 0) insert(cx, cx / 3);
		if (cx % 2 == 0) insert(cx, cx / 2);
		insert(cx, cx - 1);
	}
	
	int cur = 1;
	cout << v[1] << "\n";

	vector<int> rev;
	while (cur) {
		rev.push_back(cur);
		cur = path[cur];
	}
	reverse(rev.begin(), rev.end());

	for (int i : rev) cout << i << " ";
}

 

1까지 이동 가능한 경로를 탐색하고, 걸린 시간과 경로를 출력하는 함수

 

 

문제풀이

1. x값을 입력 받고, bfs함수를 호출한다.
2. q에 x를 추가하고, q가 빌때까지 while루프를 수행한다.
3. 매 루프마다 변수 cx에 현재 요소를 저장하고, 기저 조건으로 cx가 1일 경우 break처리한다.
4. cx가 3으로 나누어 떨어지면 insert함수에 cx, cx/3을 전달하여 이동 작업을 수행한다.
5. cx가 2으로 나누어 떨어지면 insert함수에 cx, cx/2을 전달하여 이동 작업을 수행한다.
6. insert함수에 cx, cx-1을 전달하여 이동 작업을 수행한다.
7. while문이 종료된 후 변수 cur을 1로 저장하고, v[1]을 출력 후 개행문자를 삽입한다.
8. 정수형 벡터 rev를 초기화 하고, cur이 0에 도달 할때까지 while루프를 수행한다.
9. rev에 cur을 추가하고, cur을 path[cur]로 변경한다.
10. reverse함수를 통해 rev벡터를 뒤집어 준 후 요소를 공백을 기준으로 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 1부터 경로를 rev에 추가했으므로 경로 역추적이 끝난 후엔 rev벡터를 reverse함수를 통해 뒤집어주었다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 1e6 + 1;
int x;
int v[N];
int path[N];
queue<int> q;

void insert(int cx, int nx) {
	if (1 <= nx && nx < N && !v[nx]) {
		v[nx] = v[cx] + 1;
		path[nx] = cx;
		q.push(nx);
	}
}

void bfs() {
	q.push(x);

	while (!q.empty()) {
		int cx = q.front(); q.pop();
		if (cx == 1) break;

		if (cx % 3 == 0) insert(cx, cx / 3);
		if (cx % 2 == 0) insert(cx, cx / 2);
		insert(cx, cx - 1);
	}
	
	int cur = 1;
	cout << v[1] << "\n";

	vector<int> rev;
	while (cur) {
		rev.push_back(cur);
		cur = path[cur];
	}
	reverse(rev.begin(), rev.end());

	for (int i : rev) cout << i << " ";
}

int main() {
	cin >> x;
	bfs();
}