백준 14226번 이모티콘 JAVA 구현해보기

---

```

백준 14226번 이모티콘 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 14226번 풀이

---

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

14226번: 이모티콘

 

백준 14226번 이모티콘은

난이도 골드 등급의 문제로서

 

화면에 이모티콘이 1개 있고

다음과 같은 3가지 연산을 통해 이모티콘 S 개를 만들고자 하고

 

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

 

각 연산이 1초 걸릴때

 

S개의 이모티콘을 만드는데 필요한 시간을 구하면 되는 문제입니다.

(2 이상 1000 이하의 수 S)

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

일단 스크린에 있는 이모티콘 수, 클립보드에 있는 이모티콘 수를 가지고 루트부터 하나하나 그려보았습니다.

백준 14226번 이모티콘 설명 그림

트리가 나옵니다.

 

해당되는 트리를 보시고

 

초록색으로 그려진 것처럼

 

한 줄씩 breadth-first로 검색해줍니다.

 

검색 순서는 Que를 사용해주었고

 

이미 방문한 곳은 추가로 검색하면 시간 낭비기 때문에 visits [][]라는 이중 배열로 확인을 해주었습니다.

 

조건에 맞게 클립보드에 있는 이모티콘 수와 스크린에 있는 이모티콘 수를 조절해 주었고

 

입력받은 이모티콘 수와 스크린 이모티콘수가 같다면 해당되는 시간을 출력해줍니다.

 

(시간의 경우 깊이라 생각하시면 편합니다. )

 

전체 코드는 아래와 같습니다.

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

public class Main {

    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final int kEmojiMaxCnt = 1001;

    public static void main(String[] args) throws IOException {
        int reqEmojiCount = Integer.parseInt(br.readLine());
        System.out.println(bfs(reqEmojiCount));
    }

    private static int bfs(int reqEmojiCount) {
        Queue<EmoInfo> emojiQue = new LinkedList<>();
        emojiQue.add(new EmoInfo(1, 0, 0));
        final boolean[][] visits = new boolean[kEmojiMaxCnt][kEmojiMaxCnt];
        visits[1][0] = true;
        int retVal = -1;

        while (!emojiQue.isEmpty()) {
            final EmoInfo curEmoInfo = emojiQue.remove();
            final int kScrEmoCnt = curEmoInfo.getScrEmoCnt();
            final int kCbdEmoCnt = curEmoInfo.getCbdEmoCnt();
            final int kTime = curEmoInfo.getTime();

            if (reqEmojiCount == kScrEmoCnt) {
                retVal = kTime;
                break;
            }

            if (0 < kScrEmoCnt && kScrEmoCnt < kEmojiMaxCnt) {
                // 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
                if (!visits[kScrEmoCnt][kScrEmoCnt]) {
                    visits[kScrEmoCnt][kScrEmoCnt] = true;
                    emojiQue.add(new EmoInfo(kScrEmoCnt, kScrEmoCnt, kTime + 1));
                }

                // 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
                if (kCbdEmoCnt > 0 && ((kScrEmoCnt + kCbdEmoCnt) < kEmojiMaxCnt)) {
                    if (!visits[kScrEmoCnt + kCbdEmoCnt][kCbdEmoCnt]) {
                        visits[kScrEmoCnt + kCbdEmoCnt][kCbdEmoCnt] = true;
                        emojiQue.add(new EmoInfo(kScrEmoCnt + kCbdEmoCnt, kCbdEmoCnt, kTime + 1));
                    }
                }

                // 화면에 있는 이모티콘 중 하나를 삭제한다.
                if (!visits[kScrEmoCnt - 1][kCbdEmoCnt]) {
                    visits[kScrEmoCnt - 1][kCbdEmoCnt] = true;
                    emojiQue.add(new EmoInfo(kScrEmoCnt - 1, kCbdEmoCnt, kTime + 1));
                }
            }
        }
        return retVal;
    }

    // ScrEmoCnt : screen emoticon count
    // CbdEmoCnt : clipboard emoticon count
    // time : time past in seconds
    private static class EmoInfo {
        int ScrEmoCnt;
        int CbdEmoCnt;
        int time;

        public EmoInfo(int scrEmoCnt, int cbdEmoCnt, int time) {
            ScrEmoCnt = scrEmoCnt;
            CbdEmoCnt = cbdEmoCnt;
            this.time = time;
        }

        public int getScrEmoCnt() {
            return ScrEmoCnt;
        }

        public int getCbdEmoCnt() {
            return CbdEmoCnt;
        }

        public int getTime() {
            return time;
        }
    }
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---