[백준] 14226번 : 이모티콘(JAVA)

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

14226번: 이모티콘

풀이

[화면에 있는 이모티콘 갯수, 클립보드에 있는 이모티콘 갯수] 형태로 값을 저장하면서 해당 규칙을 수행해 나가면서 bfs를 돌리면됩니다.

 

아무 입력없이 처음에 화면에 1을 입력해서 [1,0]으로 시작합니다.

 

1. 화면에 이모티콘을 클립보드에 복사 => [x, y] -> [x, x]

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 => [x, y] -> [x + y, y]

3. 화면에 있는 이모티콘 1개 삭제 => [x, y] -> [x - 1, y]

 

※ 주의할점 : 2번 수행시 y가 0보다 크거나 같고(음수이면 더하면 음수가 될 수 있으므로), x + y가 최대 크기보다 작아야 합니다.

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

		System.out.print(bfs(Integer.parseInt(br.readLine())));
	}
	
	public static int bfs(int n) {
		Queue<int[]> queue = new LinkedList<>();
		boolean[][] visited = new boolean[1001][1001];
		queue.add(new int[] {1, 0, 0});
		visited[1][0] = true;
		
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			
			if(now[0] == n) {
				return now[2];
			}
			
			if(now[0] > 0 && now[0] < 1001) {
				if(!visited[now[0]][now[0]]) {
					visited[now[0]][now[0]] = true;
					queue.add(new int[] {now[0], now[0], now[2] + 1});
				} //복사
				if(!visited[now[0] - 1][now[1]]) {
					visited[now[0] - 1][now[1]] = true;
					queue.add(new int[] {now[0] - 1, now[1], now[2] + 1});
				} //삭제
			}
			
			if(now[1] >= 0 && now[0] + now[1] < 1001) {
				if(!visited[now[0] + now[1]][now[1]]) {
					visited[now[0] + now[1]][now[1]] = true;
					queue.add(new int[] {now[0] + now[1], now[1], now[2] + 1});
				} //붙여넣기
			}
		}
		return 0;
	}
}