[백준] 14226 이모티콘 - BFS + DP JAVA

 

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

14226번: 이모티콘

코드설명

DP + BFS 문제입니다.

 

처음에는 재귀를 활용해서 모든 경우를 탐색하며 DP를 활용하려고 하였지만, 시간초과가 납니다.

BFS를 활용하여 불가능할경우 더이상 움직이지 않도록 처리해야 시간초과가 나지 않습니다.

 

BFS를 활용하여 Visited 배열을 함께 사용할경우, board가 N이 나올경우 해당 timeSec이 가장 최소의 수인 이유는 Queue를 활용해서 진행하기 때문입니다. 만약, board가 N이 나올경우 그 이후의 수는 절대 처음에 나온 timeSec보다 더 최소일 수 없습니다.

만약에 재귀를 활용하여 모든 경우를 탐색할경우 이후의 모든과정까지 모두 탐색하기에 차이가 납니다.

 

반례는 아래의 글을 추천합니다.

https://www.acmicpc.net/board/view/96939

 

코드

BFS + DP_Visited를 활용할경우

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

public class Main {
	public static int T, N, answer = Integer.MAX_VALUE;
	public static boolean[][] visited;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	visited = new boolean[2001][2001];
    	BFS();
    	System.out.println(answer);
	}
	
	public static void BFS() {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(0, 0, 1));
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			int timeSec = temp.timeSec;
			int clipBoard = temp.clipBoard;
			int board = temp.board;
			
			if(board == N) {
				answer = Math.min(answer, timeSec);
				return ;
			}
			if(visited[board][clipBoard] == true) continue;
			
			visited[board][clipBoard] = true;
			//1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
			q.offer(new Node(timeSec + 1, board, board));
			
			//2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
			if(clipBoard > 0 && clipBoard + board <= N) {
				q.offer(new Node(timeSec + 1, clipBoard, board + clipBoard));	
			}
			
			//3. 화면에 있는 이모티콘 중 하나를 삭제한다.
			if(board -1 >= 0) {
				q.offer(new Node(timeSec + 1, clipBoard, board - 1));
			}
		}
		
	}
	

}
class Node{
	int timeSec;
	int clipBoard;
	int board;
	public Node(int timeSec, int clipBoard, int board) {
		this.timeSec = timeSec;
		this.clipBoard = clipBoard;
		this.board = board;
	}
}

 

재귀 활용할경우 완전탐색을 하기에 시간초과가 납니다. 

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

public class Main {
	public static int T, N;
	public static int[][] DP;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	DP = new int[2001][2001]; //[clipboard][board]일때의 최소시간을 저장해놓습니다.
    	for(int i=0;i<DP.length;i++) {
    		Arrays.fill(DP[i], Integer.MAX_VALUE);
    	}
    	
    	System.out.println(simulate(0, 0, 1));
	}
	
	public static int simulate(int timeSec, int clipboard, int board) {
		if(DP[board][clipboard] <= timeSec) return DP[board][clipboard];

		if(timeSec > N) return Integer.MAX_VALUE; //만약 이미 시간이 N을 초과했다면 종료시킵니다.
		if(board == N) return timeSec; 		//만약 화면의 이모티콘 개수가 N개라면 timeSec을 return 하며 종료한다.  
		
		int temp1 = Integer.MAX_VALUE;
		int temp2 = Integer.MAX_VALUE;
		int temp3 = Integer.MAX_VALUE;
		
		temp1 = simulate(timeSec + 1, board, board); //1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장하는 경우
		if(clipboard > 0 && clipboard + board <= N) {
			temp2 = simulate(timeSec + 1, clipboard, board + clipboard); //2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 하는 경우	
		}
		if(board -1 >= 0 && board - 1 <= N) {
			temp3 = simulate(timeSec + 1, clipboard, board - 1); //3. 화면에 있는 이모티콘 중 하나를 삭제한다.	
		}
		return DP[board][clipboard] = Math.min(temp1, Math.min(temp2, temp3));
	}

}