[14426] 이모티콘

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

---

이모티콘 S개를 만들 때까지 3가지 연산을 계속 하는 것이기 때문에 BFS를 이용해서 풀 수 있는 문제입니다.

저는 처음에 Pair 클래스를 선언해서 화면에 있는 이모티콘 개수, 시간만 생각하고 visited 배열도 1차원으로 선언하여 화면에 있는 이모티콘의 개수만 생각해서 문제를 풀었습니다. 그래서 삭제연산을 하면 시간이 1초 증가하고, 복사 붙여넣기를 하면 시간이 2초 증가하는 방식으로 풀었는데 그렇게 풀게 되면 각 경우에 클립보드에 이모티콘 몇개가 저장되어 있는지 다르기 때문에 틀린 방법이었습니다.

그래서 Pair 클래스도 이모티콘의 개수, 클립보드에 저장되어 있는 이모티콘, 시간 3가지로 나누고, visited배열도 1차원 배열이 아닌 2차원 배열로 visited[이모티콘의개수][클립보드에저장되어있는이모티콘] 으로 나누어 풀어야 하는 문제였습니다.

[문제 풀이]

1. 처음엔 이모티콘 1개로 시작하므로 queue에 (1, 0 ,0) 을 넣습니다. 첫번 째 1 은 현재 이모티콘의 개수이고, 두번 째 0은 클립보드에 저장되어 있는 이모티콘, 세번 째 0은 현재 시간을 뜻합니다.

2. 이제 queue에 들어있는 Pair 들을 pop 하면서 BFS를 시행합니다.

① 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다 -> 문제에 이모티콘 개수의 최댓값과 최솟값의 범위에 들어올 때  "클립보드에 이모티콘을 복사하면 이전에 클립보드에 있었던 내용은 덮어쓰기가 된다." 라고 명시했기 때문에 visited[n_emotion][n_emotion] 을 검사해야 합니다.

② 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다 -> 클립보드에 있는 이모티콘과 현재 이모티콘의 개수에 더해지기 때문에 visited[이모티콘개수+클립보드의 이모티콘개수][클립보드의 이모티콘개수]를 검사해야 합니다.

③ 화면에 있는 이모티콘 중 하나를 삭제한다 -> 간단하게 현재 화면에 있는 이모티콘을 1감소 시키는 연산이기 때문에 visited[이모티콘개수-1][클립보드의 이모티콘] 을 검사합니다.

3. 위의 조건들을 만족시키면서 BFS를 실행하다가 처음에 입력받은 S값과 화면에 이모티콘이 같으면 그 때의 시간을 출력하고 종료합니다.

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

// 14226 이모티콘
public class Main {
	static int S, minute=0;
	static Queue<Pair> queue = new LinkedList<Pair>();
	static boolean visited[][] = new boolean[2000][2000];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		S = sc.nextInt();
		BFS();
	}
	
	public static void BFS() {
		queue.offer(new Pair(1, 0, 0));
		
		while(!queue.isEmpty()) {
			Pair p = queue.poll();
			
			int n_emotion = p.emotion;
			int n_clipboard = p.clipboard;
			int n_time = p.time;
			
			if(n_emotion == S) {
				System.out.println(p.time);
				return;
			} 
			
			if(n_emotion > 0 && n_emotion < 2000) {
				
				// 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
				if(!visited[n_emotion][n_emotion]) {
					visited[n_emotion][n_emotion] = true;
					queue.offer(new Pair(n_emotion, n_emotion, n_time+1));
				}
				
				// 3. 화면에 있는 이모티콘중 하나를 삭제한다.
				if(!visited[n_emotion-1][n_clipboard]) {
					visited[n_emotion-1][n_clipboard] = true;
					queue.offer(new Pair(n_emotion-1, n_clipboard, n_time+1));
				}
			}
			
			// 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
			if(n_clipboard > 0 && n_emotion+n_clipboard < 2000) {
				if(!visited[n_emotion+n_clipboard][n_clipboard]) {
					visited[n_emotion+n_clipboard][n_clipboard] = true;
					queue.offer(new Pair(n_emotion+n_clipboard,n_clipboard, n_time+1));
				}
			}
			
		}
	}
}

class Pair {
	int emotion, clipboard, time;
	Pair(int emotion, int clipboard, int time){
		this.emotion=emotion;
		this.clipboard = clipboard;
		this.time=time;
	}
	
}