백준 8111번 0과1

 

 

 

 

www.acmicpc.net/problem/8111

<접근방법>

1. 1부터 시작하여 뒤에 1, 0을 달아주며 완전탐색을 한다.

 - 탐색 시, 오버플로우가 나지 않도록 (현재 숫자 % 목표 숫자)를 넣어주도록 한다.

 - 탐색 종료 후, 만든 숫자를 출력해야하므로 트리를 만들면서 탐색한다.

 

2. 탐색 종료 후, 트리를 바텀에서부터 탑으로 향하며 만든 숫자를 출력한다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <memory.h>
using namespace std;

#define MAX 20000 + 1

int test;
int n;
int parent[MAX];
char s[MAX];


void bfs() {
	queue<int> q;
	bool visit[MAX]; memset(visit, false, sizeof(visit));

	q.push(1);
	visit[1] = true;
	parent[1] = -1;
	s[1] = '1';


	while (!q.empty()) {
		int now = q.front();
		q.pop();

		int p[2];

		p[0] = (now * 10) % n;
		p[1] = (now * 10 + 1) % n;

		for (int i = 0; i < 2; i++) {
			int next = p[i];
			if (visit[next]) continue;

			
			parent[next] = now;
			s[next] = i + '0';

			if (next == 0) return;

			q.push(next);
			visit[next] = true;;
		}
	}
}

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

	traceTree(parent[num]);
	cout << s[num];
}

int main() {
	cin >> test;
	while (test--) {
		cin >> n;
		if (n == 1) {
			cout << 1 << '\n';
			continue;
		}

		bfs();
		traceTree(0);
		cout << '\n';
	}
	
	return 0;
}