[백준] 1107 리모컨 [자바]

 

 

---

https://www.acmicpc.net/source/40117190

로그인

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
	static int min;
	static boolean broken[];
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		int N = Integer.parseInt(br.readLine());
 		int M = Integer.parseInt(br.readLine());
 		broken = new boolean[10];
 		if(M != 0) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	 		for(int i = 0; i < M; i++) {		
	 			int a = Integer.parseInt(st.nextToken());
	 			broken[a] = true;
	 		}
 		}
 		if(N == 100)
 			System.out.println(0);
 		else {
 			min = Math.abs(N-100); //시작 채널 100에서 ++ or -- 로만 눌러서 이동할려고 가는 채널을 간 경우(누른 횟수가 가장 많은 경우다)
 			for(int i = 0; i <= 1000000; i++) {
 				int a = brute(i);
 				if(a != 0) { //숫자 버튼만 눌러 만들 수 있는 경우
 					int temp = Math.abs(N-i); //만들 수 있는 수(i)에서 ++나 -- 버튼을 누른 횟수
 					min = Math.min(min, temp+a); //(만들 수 있는 수(i)의 자리수) + (i에서 ++ or -- 를 눌러 N까지 누른 횟수)
 				}
 			}
 			System.out.println(min);
 		}
  	}
 	static int brute(int n) {
 		int len = 0;
 		if(n == 0) {
 			if(broken[n]) //0버튼이 고장났으면
 				return len;
 			else
 				return 1;
 		}
 		while(n > 0) {
 			if(broken[n%10]) { //n의 자리수 중 하나가 고장나 n을 만들 수 없음
 				return 0;
 			}
 			len++;
 			n /= 10;
 		}
 		return len;
 	}
}

---

※ 아래의 코드도 가능하지만 위의 코드에 비해 메모리와 시간을 많이 잡아먹음

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
	static Integer[] dp;
	static boolean broken[];
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		int N = Integer.parseInt(br.readLine());
 		int M = Integer.parseInt(br.readLine());
 		dp = new Integer[1000001];
 		broken = new boolean[10];
 		if(M != 0) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	 		for(int i = 0; i < M; i++) {		
	 			int a = Integer.parseInt(st.nextToken());
	 			broken[a] = true;
	 		}
 		}
 		if(N == 100)
 			System.out.println(0);
 		else {
 			bfs();
 			System.out.println(dp[N]);
 		}
  	}
 	static void bfs() {
 		LinkedList<Integer> que = new LinkedList<>();
 		LinkedList<Integer> queue = new LinkedList<>();
 		queue.add(100);
 		for(int i = 0; i <= 9; i++) {
 			if(!broken[i]) {
 				dp[i] = 1;
 				que.add(i);
 				queue.add(i);
 			}
 		}
 		while(!que.isEmpty()) {
 			int temp = que.poll();
 			for(int i = 0; i <= 9; i++) {
 				int a = temp * 10 + i;
 	 			if(!broken[i] && a <= 1000000 && dp[a] == null) {
 	 				dp[a] = dp[temp] + 1;
 	 				que.add(a);
 	 				queue.add(a);
 	 			}
 	 		}
 		}
 		dp[100] = 0;
 		while(!queue.isEmpty()) {
 			int temp = queue.poll();
 			if(temp + 1 <= 500000) {
 				if(dp[temp+1] == null) {
 					dp[temp+1] = dp[temp]+1;
 					queue.add(temp+1);
 				}
 				else {
 					if(dp[temp+1] > dp[temp] + 1) {
 						dp[temp+1] = dp[temp]+1;
 						queue.add(temp+1);
 					}
 				}
 			}
 			if(temp - 1 >= 0) {
 				if(dp[temp-1] == null) {
 					dp[temp-1] = dp[temp]+1;
 					queue.add(temp-1);
 				}
 				else {
 					if(dp[temp-1] > dp[temp] + 1) {
 						dp[temp-1] = dp[temp]+1;
 						queue.add(temp-1);
 					}
 				}
 			}
 		}
 	}
}