[백준] 1107번 : 리모컨 - 자바(JAVA)

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

1107번: 리모컨

 

문제 해석

100번 채널에서 시작하여 +,-버튼을 통해 이동하려고 합니다.

이때 최소로 버튼을 눌러서 N번 채널로 이동하려고 합니다.

고장 난 버튼이 존재하여 고장 난 버튼은 누를 수 없습니다.

 

문제 풀이 전 설계

최단거리를 구해야 하기 때문에 BFS를 활용해보고자 합니다.

이미 최단거리로 만들어진 채널은 방문할 필요가 없습니다.

100번 채널에서 퍼저나가는 형식으로 시작됩니다.

 

하지만 100번에서 시작하더라도 리모컨의 버튼을 누르면 다시 1~9번부터 시작하게 되는 현상이 발생하여 100번이 무시됩니다.

 

그리고 버튼을 눌러서 만들 수 있는 모든 경우의 수도 10^6이므로 90만밖에 되지 않습니다.

 

즉, 버튼을 눌러서 만들 수 있는 모든 경우의 수를 찾고 거기서 +,-버튼을 눌러 가장 가까운 채널로 이동하는 횟수를 구하고자 합니다.

 

문제 풀이 하면서

DFS로 경우의 수를 만들어보고자 했는데 조금 복잡했습니다.

최댓값은 문제에서 500_000이라고 되어있으나 9를 제외하고 모두 고장 났다면 999999를 눌러서 찾는 경우도 포함되어야 하므로 최댓값을 999999로 설정합니다.

 

이제 0부터 999999까지 숫자를 늘려가며 번호가 고장 나지 않은 번호를 눌러서 표현할 수 있다면 그 번호에서 +,-로 값을 찾을 때 리모컨을 누르는 횟수를 계산하며 최솟값을 탐색해나갑니다.

 

코드

import java.util.*;

public class Main_리모컨_1107 {

    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);

        int target = scan.nextInt();
        int m = scan.nextInt();

        boolean[] broken = new boolean[10];
        for(int i = 0; i < m; i++) {
            int n = scan.nextInt();
            broken[n] = true;
        }

        int result = Math.abs(target - 100); //초기값 설정
        for(int i = 0; i <= 999999; i++) {
            String str = String.valueOf(i);
            int len = str.length();

            boolean isBreak = false;
            for(int j = 0; j < len; j++) {
                if(broken[str.charAt(j) - '0']) { //고장난 버튼을 눌러야 하면
                    isBreak = true;
                    break; //더 이상 탐색하지 않고 빠져나온다.
                }
            }
            if(!isBreak) { //i를 누를때 고장난 버튼을 누르지 않는다면
                int min = Math.abs(target - i) + len; //i를 누른 후(len) target까지 이동하는 횟수(target - i)
                result = Math.min(min, result);
            }
        }
        System.out.println(result);
    }
}