백준 8111 c++ "0과 1" -PlusUltraCode-

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

 

[필자 사고]

탐색 문제이다. 이 문제에서 핵심 알고리즘은 부모추적 알고리즘과 모듈러 공식 및 BFS탐색 방법인거 같다.

모듈로 공식으로 인해 방문 배열을 입력된 숫자의 나머지로 선정할수 있고,

부모추적 인덱스 즉 DFS를 이용하여 부모추적을하여 map에서 원하는 글자를 꺼내어 출력을 하면 된다.

 

한 문제에서 3가지 알고리즘을 배워서 좋은 학습 문제였다.

 

[코드 해설]

위 코드를 설명하면 다음과 같습니다:

1. BFS를 이용한 탐색 과정
   BFS 함수는 큐(myQueue)를 사용하여 모듈로 연산을 기반으로 숫자를 생성하고, 목표 상태(나머지가 0)가 될 수 있는지를 판단합니다.
   • 시작은 1 % num으로 하며, 이를 큐에 넣고 방문 표시(visited)를 합니다.
   • 큐에서 값을 꺼내 현재 나머지(nowMod)를 기준으로 다음 가능한 상태(나머지)를 계산합니다.
   • 다음 상태는 (nowMod * 10 + i) % num으로 계산되며, 여기서 i는 0 또는 1입니다.
   • 방문하지 않은 상태에 대해서는 방문 표시를 하고 큐에 삽입하며, 추적 정보(trace)와 해당 상태를 생성한 숫자(myMap)를 기록합니다.
   • 만약 현재 상태의 나머지가 0이라면, 목표 상태에 도달한 것이므로 true를 반환합니다.
2. 결과 출력 (백트래킹을 활용한 경로 추적)
   Print 함수는 trace 벡터를 사용하여 BFS 탐색 과정에서 거슬러 올라가며 생성된 숫자를 출력합니다.
   • 목표 상태에서 시작하여 trace를 따라 이전 상태로 이동하며, 각 상태를 생성한 숫자(myMap)를 기록합니다.
   • 재귀적으로 호출되므로, 가장 처음 생성된 상태부터 출력됩니다.
3. 초기화
   InitVector 함수는 입력된 숫자(num)에 대해 방문 벡터(visited), 추적 벡터(trace), 숫자 매핑(myMap)을 초기화합니다.
   • 입력값에 따라 벡터 크기를 재설정하고 이전 데이터는 모두 초기화합니다.
4. 게임 시작
   Game_Start 함수는 입력받은 테스트 케이스 개수(T)만큼 숫자를 입력받아 처리합니다.
   • 각 숫자에 대해 BFS를 실행하며, 목표 상태에 도달하면 Print 함수로 결과를 출력하고, 도달할 수 없으면 "BRAK"을 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

vector<bool> visited;
vector<int> trace;
map<int, char>myMap;



bool BFS(int num) {
	queue<int> myQueue;
	myQueue.push(1%num);
	visited[1%num] = true;
	trace[1 % num] = -1;
	myMap[1%num] = '1';
	while (!myQueue.empty()) {
		int nowMod = myQueue.front();
		myQueue.pop();

		if (nowMod == 0) {
			return true;
		}

		for (int i = 0; i < 2; i++) {
			int nextMod = (nowMod * 10 + i) % num;
		
			if (!visited[nextMod]) {
				visited[nextMod] = true;
				myQueue.push(nextMod);
				trace[nextMod] = nowMod;
				myMap[nextMod] = '0' + i;

			}
		}
	}
	return false;
}

void Print(int num) {
	if (num ==-1)return;

	Print(trace[num]);
	cout << myMap[num];
}

void InitVector(int N) {
	visited.clear();
	visited.resize(N);
	trace.clear();
	trace.resize(N );
	myMap.clear();
}

void Game_Start() {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int num;
		cin >> num;
		InitVector(num);

		if (BFS(num)) {
			Print(0);
			cout << '\n';
		}
		else {
			cout << "BRAK" << '\n';
		}
	}
}

int main(void) {
	Game_Start();
}