[코딩테스트][백준] 🔥 백준 8111번 "0과 1" 문제: Java으로 완벽 해결하기! 🔥

문제 링크

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

미해결

• 풀이시간 : BFS이상의 접근 방법을 못찾음
• 수학... 모듈러... : 모듈러 법칙을 모르면 풀수가 없었던 문제였다... 당연히 0과 1을 붙이는 BFS 정도까지만 생각했고 그 이상의 접근 법이 아무리 잡고 있어도 생각이 안나서 포기하고 답지를 보았다.
• 풀이 : 모듈러 법칙이란 A%B=C 일 때, C%B=C이라는 느낌이다. 여기서 공통적으로 나누어지는 수에 공통적으로 +, x 연산을 하여도 나머지값은 같다는 뜻이다. 문제에서는 N으로 문제를 나누어서 0인 경우, 즉 N으로 나누어떨어지는 경우를 찾는 문제인데, 우리는 각 숫자의 뒤에 0과 1을 붙이는 과정을 +, x 연산으로 나타낼 수가 있다. x10을 한다면 0이 붙는 것이고 x10+1을 한다면 1이 붙는 것이다. 즉, 숫자의 길이가 증가하더라도 x, + 연산을 추가적으로 한다음 나머지 연산을 하는 것이라면 하나의 종류의 나머지 값은 한번만 나온다는 의미가 된다. 그렇기 때문에 이 것을 visited로 두고 찾아 나가면 되는 것이다. 그렇기에 visited의 범위가 N의 최대 범위인 20,000 밖에 되지 않고 방문했던 곳을 방문하지 않는 BFS의 특징으로 인하여 연산이 가지치기가 되서 줄어드는 것이다.
  이 때, 우리는 나머지를 가지고 방문 처리를 하지만 문자열 또한 정답으로 출력해야 하므로 이를 가지고 가면 된다. 어차피 같이 가지고 가는 나머지 값이 한번밖에 나올 수 없기 때문에 문제가 되지 않는다.

🕒 Java 풀이시간: x

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int T= Integer.parseInt(st.nextToken());

        StringBuilder sb=new StringBuilder();
        for(int i=0;i<T;i++){
            st=new StringTokenizer(br.readLine());
            int N=Integer.parseInt(st.nextToken());
            sb.append(bfs(N));
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    static class Pair{
        String str;
        int num;
        public Pair(String str,int num){
            this.str=str;
            this.num=num;
        }
    }
    
    public static String bfs(int num){
        Deque<Pair> q=new ArrayDeque<>();
        boolean[] visited=new boolean[20001];
        q.add(new Pair("1",1));
        while(!q.isEmpty()){
            Pair cur=q.poll();
            int curNum=cur.num;
            String curStr=cur.str;
            if(curNum==0){
                return curStr;
            }
            if(curStr.length()>100){
                return "BRAK";
            }
            int plusZero=(curNum*10)%num;
            if(!visited[plusZero]){
                visited[plusZero]=true;
                q.add(new Pair(curStr+"0",plusZero));
            }
            int plusOne=(curNum*10+1)%num;
            if(!visited[plusOne]){
                visited[plusOne]=true;
                q.add(new Pair(curStr+"1",plusOne));
            }
        }
        return "BRAK";
    }
}

이렇게 Java으로 백준의 "0과 1" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊