[Java] 백준 14226 : 이모티콘

[Java] 백준 14226 : 이모티콘

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

14226번: 이모티콘

---

접근

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

 

화면에 있는 이모티콘의 수를 x, 클립보드에 있는 이모티콘의 수를 y라고 가정한다.

복사 -> 클립보드 저장의 경우: [x, y] -> [x, x]

붙여넣기의 경우: [x, y] -> [x+y, y]

화면에서 하나 삭제의 경우: [x, y] -> [x-1, y]

 

bfs를 활용한다고 가정하면, 이차원 배열에서 탐색해야 할 그래프는 x, y의 모든 경우의 수라고 할 수 있다.

큐에서 뽑은 값이 [x, x]인 경우 -> 방문처리를 하고 시간 + 1을 하고 큐에 다시 넣는다.

큐에서 뽑은 값이 [x+y, y]인 경우 -> 방문처리를 하고 시간 + 1을 하고 큐에 다시 넣는다.

큐에서 뽑은 값이 [x-1, y]인 경우 -> 방문처리를 하고 시간 + 1을 하고 큐에 다시 넣는다.

 

만약 붙여넣기를 하려는 경우, x+y의 값이 그래프의 범위를 넘지 않았는지, y가 0보다 큰지(붙여넣기를 하려면 클립보드에 1개 이상의 이모티콘이 있어야 한다.) 체크를 하고 진행해야 한다.

 

코드

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.println(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[] pick = queue.poll();

            if(pick[0] == n) { // 현재 값이 만들려는 이모티콘 개수와 같은 경우 기록된 시간을 리턴
                return pick[2];
            }

            if(pick[0] > 0 && pick[0] < 1001) { // 이모티콘 경우의 수의 범위 내에서 설정
                if(!visited[pick[0]][pick[0]]) {
                    visited[pick[0]][pick[0]] = true;
                    queue.add(new int[] {pick[0], pick[0], pick[2] + 1});
                } // 복사의 경우

                if(!visited[pick[0] - 1][pick[1]]) {
                    visited[pick[0] - 1][pick[1]] = true;
                    queue.add(new int[] {pick[0] - 1, pick[1], pick[2] + 1});
                } // 삭제의 경우

                if(pick[0] + pick[1] < 1001 && pick[1] > 0) { // x+y가 그래프 값 범위인가? 클립보드에 이모티콘이 1개 이상 있는가?
                    if (!visited[pick[0] + pick[1]][pick[1]]) {
                        visited[pick[0] + pick[1]][pick[1]] = true;
                        queue.add(new int[]{pick[0] + pick[1], pick[1], pick[2] + 1});
                    } // 붙여넣기
                }
            }
        }
        return 0;
    }
}