[백준] 8111번 0과 1

문제 설명

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

문제 풀이

• modular 연산의 성질과 BFS를 이용하여 풀이하였다.
• 문제에서 0과 1로 구성된 숫자를 체크하여 mod N 값이 0인 숫자를 찾아야한다.
  따라서 큐를 이용하여 1부터 현재 숫자x10 / 현재 숫자x10 + 1을 큐에 넣으며 수를 구성하였는데
  이렇게 단순 탐색을 했을 때 시간초과가 날 것이 당연하기 때문에 (숫자 최대 길이 100) 가지치기를 수행해야한다.
• 아래와 같은 modular 연산의 특징으로 인해 특정 숫자를 큐에 넣을 때 modular 연산을 해준 값을 넣어준다. 이때 해당 값으로 방문 체크를 하여 bfs를 수행하면 최대 20000번의 탐색으로 결과 도출이 가능하다.

X, Y 값이 (X mod N) = (Y mod N)을 만족할 때
(X x 10 + 1) mod N = (Y x 10 + 1) mod N
(X x 10) mod N = (Y x 10) mod N
이라는 식이 성립하게 된다 따라서 bfs 진행 중 X, Y 중 하나는 가지치기가 가능하다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int T, N;

    public static class Point {
        String str;
        int num;
        public Point(String str, int num) {
            this.str = str;
            this.num = num;
        }
    }

    public static String solve() {
        boolean[] chk = new boolean[N+1];
        Queue<Point> q = new ArrayDeque<>();
        //뺴도 될지 확인
        if (N == 1) return "1";
        chk[1] = true;
        q.add(new Point("1", 1));
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.num == 0) return cur.str;
            int nextNum;
            // 0붙이기
            nextNum = cur.num * 10;
            nextNum = nextNum % N;
            if (!chk[nextNum]) {
                chk[nextNum] = true;
                q.add(new Point(cur.str.concat("0"), nextNum));
            }
            // 1붙이기
            nextNum = cur.num * 10 + 1;
            nextNum = nextNum % N;
            if (!chk[nextNum]) {
                chk[nextNum] = true;
                q.add(new Point(cur.str.concat("1"), nextNum));
            }
        }
        return "BRAK";
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            bw.write(solve() + "\n");
        }
        bw.flush();
        bw.close();
        bw.close();
    }
}