[백준, Java] 14226번 : 이모티콘

🔗 문제 링크

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

😮 문제 해결 방법

BFS를 이용한 완전 탐색 방식으로 문제를 해결했다.

1. 최초의 경우에는 화면에만 이모티콘이 있으므로 큐에 넣고 시작한다.
2. 현재 시간에만 할 수 있는 행동을 구분하기 위해서 큐의 사이즈만큼만 현재 초에는 반복을 돌게 한다.
3. 각각의 행동은 아래와 같은 조건에 따라서 할지 말지 구분할 수 있다.
   • 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
     • 보내려는 이모티콘 개수보다 화면에 있는 이모티콘의 개수가 더 적은 경우에 이모티콘을 복사하는 것이 의미있다.
   • 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
     • 보내려는 이모티콘 개수보다 화면에 있는 이모티콘의 개수가 더 적은 경우에 이모티콘을 클립보드로 가져가고 화면에 있는 이모티콘 개수가 1개 이상이어야 한다.
   • 화면에 있는 이모티콘 중 하나를 삭제한다.
     • 화면에 있는 이모티콘 개수가 1개 이상이어야 한다.
4. 모든 행동은 [화면의 이모티콘 개수]와 [클립보드 이모티콘 개수]를 체크해 중복인 경우는 큐에 넣지 않도록 한다. → 2차원 배열을 이용한 중복 체크
5. 매 초다마 큐 사이즈는 현재 초에 행해지는 행동들이기 때문에 이모티콘 개수가 S가 되는 최초의 경우가 최소로 만들 수 있는 시간이다.

✔️  큐에 들어가는 원소의 중복을 제거해주는 부분이 중요하다.

🚩 Java 코드

package com.second.algorithm.baekjoon;

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

public class Main_14226_이모티콘 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(br.readLine());

        int rst = sendEmoticon(S);
        System.out.println(rst);

        br.close();
    }

    private static int sendEmoticon(int s) {
        boolean[][] check = new boolean[2000][1001];        // 스크린에 999, 클립보드에 999인 경우 최대
        Queue<Emoticon> queue = new LinkedList<>();
        queue.add(new Emoticon(1, 0));

        int second = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int loop = 0; loop < size; loop++) {
                Emoticon emoticon = queue.poll();
                int screenEmoticon = emoticon.getScreenEmoticon();
                int clipboardEmoticon = emoticon.getClipboardEmoticon();

                // 화면에 저장된 이모티콘 개수가 동일한 경우 최초 경우
                if (screenEmoticon == s) return second;

                // 화면에 있는 이모티콘이 보내려는 이모티콘보다 작은 경우에만 클리보드에서 복사해서 붙히기
                if (screenEmoticon < s && !check[screenEmoticon + clipboardEmoticon][clipboardEmoticon]) {
                    check[screenEmoticon + clipboardEmoticon][clipboardEmoticon]= true;
                    queue.add(new Emoticon(screenEmoticon + clipboardEmoticon, clipboardEmoticon));
                }

                if (screenEmoticon > 0) {
                    // 화면에서 한개 지우기
                    if (!check[screenEmoticon - 1][clipboardEmoticon]) {
                        check[screenEmoticon - 1][clipboardEmoticon] = true;
                        queue.add(new Emoticon(screenEmoticon - 1, clipboardEmoticon));
                    }

                    // 화면에서 클립보드로 복사하기 (화면 이모티콘이 보내려는 이모티콘 개수 보다 작은 경우에만 복사)
                    if (screenEmoticon < s && !check[screenEmoticon][screenEmoticon]) {
                        check[screenEmoticon][screenEmoticon] = true;
                        queue.add(new Emoticon(screenEmoticon, screenEmoticon));
                    }
                }
            }
            second++;
        }

        return second;
    }

    static class Emoticon {
        private int screenEmoticon;
        private int clipboardEmoticon;

        public Emoticon(int screenEmoticon, int clipboardEmoticon) {
            this.screenEmoticon = screenEmoticon;
            this.clipboardEmoticon = clipboardEmoticon;
        }

        public int getScreenEmoticon() {
            return screenEmoticon;
        }

        public int getClipboardEmoticon() {
            return clipboardEmoticon;
        }
    }
}