[백준] 1107. 리모컨 (Java)

 

1107번: 리모컨

 

풀이

• 반례가 엄청 많이 존재하니 혹시라도 틀렸다면 질문게시판의 반례모음집 게시글을 참조하며 고쳐나가면 좋다.
• 어떻게 풀지 생각하다 BFS N부터 시작해서 100까지 가는 방법을 찾았다.

문제 분류는 브루트포스로 되어있는데 말 그대로 브루트포스로 0부터 1000000까지 모든 경우를 계산하는 방법도 있다.

• N에서 출발하는데 현재 숫자가 누를 수 있는 번호이면 (isPossibleToPress(int n)으로 각 자릿수에 누를 수 없는 수가 있는지 찾기) 해당 숫자에 도달하기까지의 카운트 값을 저장하고 리턴한다.
  • 이때 |이미 저장된 누를 수 있는 번호 - N| 보다 |누를 수 있는 번호 - N|값이 작거나 같고 카운트 값도 작거나 같을 경우에만 업데이트한다.
• 누를 수 없다면 +1, -1 조작을 통해 갈 수 있으면 큐에 넣고 카운트를 1 증가시킨다.
  • 이때 현재 숫자가 UPPER_BOUND이면 +1을 하지 말고 넘기고 0이면 -1을 하지 말고 넘긴다.
• 마지막에 답을 출력할 때 현재 카운트 값을 아래 세 값중 가장 작은 값으로 업데이트 한다.
  1. 현재 카운트 값 + |누를 수 있는 번호 - 100|
  2. 현재 카운트 값 + |누를 수 있는 번호의 자릿수|
  3. |N - 100|

 

 

코드

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

public class Main {
    static int N, M, res, ans;
    static boolean[] brokenBtn = new boolean[10];
    static Map<Integer, Boolean> visited = new HashMap<>();
    static final int UPPER_BOUND = 1000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        ans = res = UPPER_BOUND;
        if (M > 0) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++)
                brokenBtn[Integer.parseInt(st.nextToken())] = true;
        }
        if (N == 100) bw.write(String.valueOf(0));
        else {
            solve();
            ans += Math.min(Math.abs(100 - res), Integer.toString(res).length());
            ans = Math.min(Math.abs(100 - N), ans);
            bw.write(String.valueOf(ans));
        }
        br.close();
        bw.close();
    }

    public static void solve() {
        Queue<Num> q = new LinkedList<>();
        q.offer(new Num(N, 0));
        while (!q.isEmpty()) {
            int num = q.peek().num;
            int cnt = q.peek().cnt;
            q.poll();

            if (isPossibleToPress(num)) {
                if (Math.abs(num - N) <= Math.abs(res - N) && cnt <= ans && num < res) {
                    res = num;
                    ans = cnt;
                }
//                System.out.println("num, cnt = " + num + ", " + cnt);
                continue;
            }

            int nextNum = num + 1;
            if (nextNum == UPPER_BOUND) continue;
            if (visited.get(nextNum) == null) {
                visited.put(nextNum, true);
                q.offer(new Num(nextNum, cnt + 1));
            }

            if (num == 0) continue;
            nextNum = num - 1;
            if (visited.get(nextNum) == null) {
                visited.put(nextNum, true);
                q.offer(new Num(nextNum, cnt + 1));
            }
        }
    }

    public static boolean isPossibleToPress(int n) {
        String num = Integer.toString(n);
        for (int i = num.length() - 1; i >= 0; i--) {
            int digit = Character.getNumericValue(num.charAt(i));
            if (brokenBtn[digit]) return false;
        }
        return true;
    }

    static class Num {
        int num;
        int cnt;

        public Num(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}