[백준] G5 1107 리모컨 (java)

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

1107번: 리모컨

 

첫번째 풀이 - 매우 비효율

 

0) 준비물

• class( 채널번호, 키 입력 회수, 방향키를 눌렀는지 여부 ) 
• boolean isVisited[1000000][2] (방향키를 눌렀을경우와 안눌렀을 경우)
• bfs()

1) 방향키를 누르는 순간 더이상 숫자키를 누를수 없다.

2) bfs() 의 Queue에 (100, 0, true) 와 (살아있는 숫자키, 1, false)를 넣는다.

3) Queue.isEmpty() 가 true 가 될때까지 poll()

4) 모든 경우를 다 queue에 삽입한다. front.flag 가 false 일경우 숫자키와 방향키를 둘다 입력가능하지만 true일 경우 방향키만 입력할 수 있다.

5) front 가 N 이 되면 탈출한다.

6) 5 의 front.cnt 가 정답이다.

 

주의사항

 

1) bfs는 반드시 방문체크를 해야한다. 처음에 방문체크를 하지 않았을 때 엄청난 시간초과가 나서 질문을 올렸더니 다음과 같은 답변이 돌아왔다. 다시한번 감사합니다.

2) 입력 중 b 의 값이 0일 경우 처리를 하지 않는다면 NullPointerException 이 날 수 있다.

3) 범위를 1000000 까지 해야한다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G5_1107_리모컨 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int channel[] = new int[1000001], N;
	static boolean keys[], isVisited[][] = new boolean[1000001][2];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		keys = new boolean[10]; // 0,1,2,3,4,5,6,7,8,9
		int b = Integer.parseInt(input.readLine());
		Arrays.fill(keys, true);
		Arrays.fill(channel,Integer.MAX_VALUE);
		
		if(b != 0) {
			tokens = new StringTokenizer(input.readLine());
			for(int i=0; i<b; i++) {
				keys[Integer.parseInt(tokens.nextToken())] = false;
			}
		}
		
		bfs();
		System.out.println(channel[N]);
	}
	private static void bfs() {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(new Node(100, 0, true));
		isVisited[100][1] = true;
		for(int i=0; i<10; i++) {
			if(keys[i]) {
				queue.offer(new Node(i, 1, false));
				isVisited[i][0] = true;
			}
		}
		
		
		while(!queue.isEmpty()) {
			Node front = queue.poll();
			if(front.num == N) {
				channel[front.num] = front.cnt;
				break;
			}
			if(channel[front.num] > front.cnt) {
				channel[front.num] = front.cnt;
			}
			if(!front.flag) {
				for(int i=0; i<10; i++) {
					if(keys[i]) {
						String str = Integer.toString(front.num) + i; 
						int next = Integer.parseInt(str);
						if(isIn(next) && !isVisited[next][0]) {
							isVisited[next][0] = true;
							queue.offer(new Node(next, front.cnt+1, false));
						}
					}
				}
			}
			if(isIn(front.num+1) && !isVisited[front.num+1][1]) {
				isVisited[front.num+1][1] = true;
				queue.offer(new Node(front.num+1, front.cnt+1, true));
			}
			if(front.num != 0 && !isVisited[front.num-1][1]) {
				isVisited[front.num-1][1] = true;
				queue.offer(new Node(front.num-1, front.cnt+1, true));
			}
		}
	}
	static class Node{
		int num;
		int cnt;
		boolean flag;
		public Node(int num, int cnt, boolean flag) {
			super();
			this.num = num;
			this.cnt = cnt;
			this.flag = flag;
		}
		@Override
		public String toString() {
			return "Node [num=" + num + ", cnt=" + cnt + ", flag=" + flag + "]";
		}
	}
	static boolean isIn(int num) {
		return (num>=0 && num<1000001);
	}
	static String src =
			"101\r\n"
			+ "0\r\n"
			+ "1";
}

 

두번째 풀이

 

1) 채널 N에 도달하는 경우는 현재 채널 100 에서 방향키로 가는 경우 |N-100| 번 입력하는 경우와

2) 고장나지 않은 숫자키를 눌러서 갈 수 있으면서 N번에 가장 가까운 채널 i + |N-i| 이다.

3) 즉 |N-100| 과 i + |N-i| 의 최소값이 정답이다.

 

주의사항

 

1) while 탈출조건을 고려해 i 가 0 일 경우를 따로 빼줘야 한다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_G5_1107_리모컨2 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		int N  = Integer.parseInt(input.readLine());
		boolean keys[] = new boolean[10]; // 0,1,2,3,4,5,6,7,8,9
		int b = Integer.parseInt(input.readLine());
		Arrays.fill(keys, true);
		
		if(b != 0) {
			tokens = new StringTokenizer(input.readLine());
			for(int i=0; i<b; i++) {
				keys[Integer.parseInt(tokens.nextToken())] = false;
			}
		}
		int answer = Math.abs(N-100); // 초기 상태. 방향키로만 이동할 경우
		
		for(int i=0; i<=1000000; i++) {
			int len = check(i, keys);
			if(len > 0) {
				if(answer > len + Math.abs(i - N)) {
					answer = len + Math.abs(i - N);
				}
			}
		}
		System.out.println(answer);
	}

	private static int check(int n, boolean keys[]) {
		int cnt = 0;
		if(n == 0) {
			if(keys[0]) {
				return 1;
			}
		}
		while(n>0) {
			if(keys[n%10]) {
				cnt++;
				n /= 10;
			}else {
				return 0;
			}
		}
		return cnt;
	}
	static String src =
			"0\r\n"
			+ "3\r\n"
			+ "0 1 2\r\n"
			+ "4";
}

 

후기

 

 8달 전에 도전했다가 실패한 문제였다. 최근에 다시 문제를 보게되어 가벼운 마음으로 풀어봤는데 생각보다 어려운 문제여서 당황했다.

질문 검색시 리모컨을 부수고 싶다는 글이 많다. 나도 그중 하나였다. 예외 케이스가 생각보다 많은 문제였고 첫 시도때 에는 bfs로 풀어서 시간이 오래걸렸다. 하지만 시간이 빠른 사람들의 코드를 보니 훨씬더 간단한 방법이 있었고 정말 감탄스러웠다. 좀더 정진하여 효율적인 코딩을 할 수 있도록 해야겠다.