[JAVA] 백준, 14226번 이모티콘

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

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static Queue<Node> que;
    static boolean[][] visited;
    static int s;

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

        s = Integer.parseInt(br.readLine());
        que = new LinkedList<>();
        visited = new boolean[1001][1001]; // [화면에 출력된 이모티콘 개수][클립보드에 저장된 이모티콘 개수]

        que.offer(new Node(1, 0, 0)); // 초기값
        visited[1][0] = true;

        System.out.println(bfs());
    }

    static int bfs() {
        while (!que.isEmpty()) {
            Node node = que.poll();

            if (node.printedNum == s) {
                return node.time;
            }

            // 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
            /**
             * 조건1. 화면에 출력된 이모티콘을 클립보드에 복사하면, 이전에 저장되어 있던 클립보드는 초기화된다.
             */
            if (node.printedNum <= 1000 && isNotVisitedFromCopyClipBoard(node)) {
                que.offer(new Node(node.printedNum, node.printedNum, node.time + 1));
                visited[node.printedNum][node.printedNum] = true;
            }

            // 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
            /**
             * 조건1. 클립 보드가 비어있으면 안 된다.
             * 조건2. 2번을 수행한 Node가 이미 방문한 Node이면 안 된다.
             */
            if (node.clipboardNum > 0 && node.printedNum + node.clipboardNum <= 1000
                && isNotVisitedFromAddPrint(node)) {
                que.offer(new Node(node.printedNum + node.clipboardNum, node.clipboardNum,
                    node.time + 1));
                visited[node.printedNum + node.clipboardNum][node.clipboardNum] = true;
            }

            // 3. 화면에 있는 이모티콘 중 하나를 삭제한다.
            /**
             * 조건1. 화면에 출력된 이모티콘이 비어있으면 안 된다.
             * 조건2. 3번을 수행한 Node가 이미 방문한 Node이면 안 된다.
             */
            if (node.printedNum > 0 && isNotVisitedFromRemovePrint(node)) {
                que.offer(new Node(node.printedNum - 1, node.clipboardNum, node.time + 1));
                visited[node.printedNum - 1][node.clipboardNum] = true;
            }
        }

        return -1;
    }

    static class Node {

        int printedNum; // 현재 화면에 출력된 이모티콘 개수
        int clipboardNum; // 현재 클립보드에 저장된 이모티콘 개수
        int time; // 현재까지 발생된 시간

        public Node(int printedNum, int clipboardNum, int time) {
            this.printedNum = printedNum;
            this.clipboardNum = clipboardNum;
            this.time = time;
        }
    }

    static boolean isNotVisitedFromCopyClipBoard(Node node) {
        return !visited[node.printedNum][node.printedNum];
    }

    static boolean isNotVisitedFromAddPrint(Node node) {
        return !visited[node.printedNum + node.clipboardNum][node.clipboardNum];
    }

    static boolean isNotVisitedFromRemovePrint(Node node) {
        return !visited[node.printedNum - 1][node.clipboardNum];
    }
}