[백준_1107번] 리모컨

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

1107번: 리모컨

[문제]

 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.  수빈이가 지금 보고 있는 채널은 100번이다.

 

[입력 조건]

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.

 

[코드]

import java.util.*;

public class BaekJoon_1107 {
	static boolean[] broken=new boolean[10];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		
		for(int i=0;i<m;i++) {
			int num=sc.nextInt();
			
			broken[num]=true;
		}
		
		int min=Math.abs(n-100); // +,- 버튼으로만 누르는 경우, 시작 채널은 100번
		for(int i=0;i<=1000000;i++) { // 0~1000000까지 완전탐색
			int len=press(i); // i를 숫자버튼으로 누를수 있는지, 누를수 있다면 몇번 눌러야 하는지 구하기
			// len이 0보다 커야 숫자 버튼으로 i를 누를수 있음을 의미
			if(len>0) {
				int count=Math.abs(n-i); // +,- 버튼을 누르르 횟수
				min=Math.min(min,len+count); // 기존의 min 값과 숫자버튼+(+,-)버튼 누른 횟수중 작은 값으로 갱신
			}
		}
		
		System.out.println(min);
	}
	
	// num 숫자를 숫자버튼으로 누를 수 있는지 확인하는 함수
	static int press(int num) {
		if(num==0) { // num이 0일 경우 예외처리
			if(broken[0])
				return 0;
			else 
				return 1;
		}
		
		int count=0;
		while(num>0) {
			if(broken[num%10]) // num중 고장난 숫자가 포함됐다면 누를수 없으므로 return 0
				return 0;
			
			count+=1; // 누르는 숫자의 갯수 증가
			num/=10; // 다음에 탐색할 숫자
		}
		
		return count; // 최종적으로는 num을 숫자버튼으로만 누를 수 있다면 num의 자릿수가 return 된다.
	}
}

 

[고찰]

 이번 문제를 처음에는 BFS로 풀어보려 했지만 해당 알고리즘으로는 최대한 누르려는 채널(n)에 우선 가까이 가는게 중요한 부분을 해결할 방법이 떠오르지 않았다. 좀 더 생각을 해보니 단순히 우선 누를수 있는 숫자 버튼을 사용하여 n에 가장 가깝게 숫자를 누르고 그 뒤부터는 +나 -버튼는 사용하면 되는 문제였다. 이 과정은 완전 탐색으로 해결할 수 있었다. 

 수빈이는 초기값 채널 100에서 시작하기 때문에 우선 +나 -로만 n번째 채널에 가기위해 눌러야 하는 버튼의 값(Math.abs(n-100))으로 min을 초기화 한다. 이후 완전탐색으로 0부터 시작하면서 해당 숫자를 숫자버튼으로만 누를수 있는지, 누를수 있다면 몇 개의 숫자버튼을 눌러야 하는지 구한 후, + 또는 - 버튼으로 움직이는 경우를 더한 값을 min 값과 비교해 더 작은 값으로 갱신하면 된다.