[백준 8111] 0과1 (JAVA)

문제

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

풀이

BFS 이용하면 풀 수 있으나 필터를 따로 해주지 않으면 메모리 초과나 시간 초과가 발생할 수 있습니다. 배수 계산 후 일의 자리만 확인하고 1이나 0인 경우만 통과시키면 경우의 수를 줄일 수 있습니다.

숫자가 17인 경우
1) n + (n * i)를 이용해 (0≤i<10) 계산합니다.
=> 17, 34, 51, 68 ...
2) 10으로 나눈 나머지가 1또는 0인 경우만 10으로 나눈 후 큐에 넣습니다. (51을 5로 바꾼 후 나머지는 string으로 저장 후 큐에 넣기)
3) 큐에서 꺼낼 때 0이 나올 때까지 1)을 반복합니다.

코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Queue<Data> q = new LinkedList<>();
        boolean[] visited;

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            q.clear();
            int num = Integer.parseInt(br.readLine());
            visited = new boolean[num + 1];
            visited[num] = true;
            boolean isFind = false;

            for (int i = 1; i < 10; i++) {
                int calc = num * i;
                if (calc % 10 == 1) {
                    q.add(new Data(calc / 10, "", "1"));
                    visited[calc / 10] = true;
                } else if (calc % 10 == 0) {
                    q.add(new Data(calc / 10, "", "0"));
                    visited[calc / 10] = true;
                }
            }

            while (!q.isEmpty()) {
                Data data = q.poll();

                if (data.sb.length() > 100) continue;
                if (data.num == num) continue;

                if (data.num == 0) {
                    bw.write(data.sb + "\n");
                    isFind = true;
                    break;
                }
                for (int i = 0; i < 10; i++) {
                    int calc = data.num + (num * i);
                    int div = calc / 10;
                    if (!visited[div]) {
                        if (calc % 10 == 1) {
                            q.add(new Data(calc / 10, data.sb.toString(), "1"));
                            visited[div] = true;
                        } else if (calc % 10 == 0) {
                            q.add(new Data(calc / 10, data.sb.toString(), "0"));
                            visited[div] = true;
                        }
                    }
                }
            }

            if (!isFind) {
                bw.write("BRAK\n");
            }
        }

        bw.close();
        br.close();
    }

    public static class Data {

        int num;
        StringBuilder sb;

        public Data(int num, String s, String add) {
            this.num = num;
            sb = new StringBuilder(s);
            sb.insert(0, add);
        }
    }
}