백준 8111번 0과 1

문제 링크입니다: https://www.acmicpc.net/problem/8111

BFS(Breadth First Search) 알고리즘을 적용하여 푸는 문제였습니다.

결과가 100의 자리 숫자가 나올 수 있었기 때문에 메모리 초과가 엄청 발생했던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 1은 1로만 이루어져 있는 숫자이기 때문에 1을 출력해줍니다.

2. N이 1이 아니라면 1부터 큐에 넣고 BFS를 시작합니다.

3. 0과 1로만 이루어져 있어야하기 때문에 큐에서 제일 앞에 있는 숫자에서 10을 곱한 숫자와 (10을 곱한 숫자 + 1)을 큐에 넣어줍니다.

i) 여기서 핵심 포인트는 오버플로우를 방지하기 위해 큐에 넣을 숫자들을 N으로 나누었을 때 나머지를 넣어주는 것입니다.

ii) 그리고 visited 배열을 통해 이미 큐에 넣었던 숫자들은 배제합니다.

4. 큐에 넣었던 숫자들 중 0이 있다면 N으로 나누어 떨어졌다는 소리이므로 BFS를 멈춥니다.

5. printPath 함수를 통해 해당 숫자들을 역순으로 출력해주면 정답입니다.(트리를 역순으로 출력해준다고 생각해주면 됩니다)

#include <iostream>

#include <queue>

#include <cstring>

using namespace std;

 

const int MAX = 20000 + 1;

 

int N;

pair<int, char> arr[MAX];

bool visited[MAX];

 

void BFS(void)

{

        queue<int> q;

        //1부터 시작

        q.push(1);

        visited[1] = true;

        arr[1].first = -1;

        arr[1].second = '1';

 

        while (!q.empty())

        {

                 int temp = q.front();

                 q.pop();

 

                 int p[2];

                 //10을 곱하면 0 추가

                 //10 곱하고 1 더해주면 1 추가

                 p[0] = (temp * 10) % N;

                 p[1] = (p[0] + 1) % N;

 

                 for (int i = 0; i < 2; i++)

                 {

                         if (!visited[p[i]])

                         {

                                 arr[p[i]].first = temp;

                                 arr[p[i]].second = i + '0';

                                 //N으로 나누어 떨어지면

                                 if (!p[i])

                                          return;

                                 visited[p[i]] = true;

                                 q.push(p[i]);

                         }

                 }

        }

}

 

//역순으로 출력

void printPath(int num)

{

        //기저 사례: 1까지 도달

        if (num == -1)

                 return;

 

        printPath(arr[num].first);

        cout << arr[num].second;

}

 

int main() {

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

        for(int t=0; t<test_case; t++)

        {

                 cin >> N;

                 //1인 경우 1 바로 출력

                 if (N == 1)

                 {

                         cout << 1 << "\n";

                         continue;

                 }

                 memset(visited, false, sizeof(visited));

 

                 BFS();

                 printPath(0);

                 cout << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~