[Algorithm/Java][백준] 14226번 이모티콘

[BOJ] 14226번 이모티콘

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

문제 접근

화면에 있는 이모티콘을 S개 만드는 최소 시간을 구하는 문제이다.
화면에 있는 이모티콘 개수와 클립보드에 있는 이모티콘 개수 그리고 시간 정보를 저장할 수 있는 Emoticon 클래스를 만들고 isVisited 배열을 화면에 있는 이모티콘 수와 클립보드에 있는 이모티콘 수를 고려할 수 있도록 2차원 배열로 만들었다.
그리고 BFS를 이용해서 화면에 있는 이모티콘을 클립보드에 저장하는 경우, 화면에 있는 이모티콘 한개를 제거하는 경우, 클립보드에 있는 이모티콘을 붙여넣는 경우 세가지를 고려해서 문제를 해결했다.

문제를 보고 이차원 배열로 해결할 생각을 하지 못해서 푸는데 꽤나 오래걸렸다...근데 이차원 배열을 사용하니까 다른 문제와 마찬가지로 굉장히 쉽게 풀렸다!
클린 코드라는 책을 읽고 있는데 변수나 함수 이름을 지을 때는 이름을 보고 이 변수나 함수가 어떤 일을 하는지 알아볼 수 있도록 짓는 것이 좋다고 해서 최대한 노력하고 있다!

Code

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ14226 {
    static int target;
    static boolean[][] isVisited = new boolean[5000][5000]; // [화면에 있는 이모티콘 수][클립보드에 있는 이모티콘 수]
    static class Emoticon {
        int countOnScreen; // 화면에 있는 이모티콘 개수
        int countOnClipboard; // 클립보드에 있는 이모티콘 개수
        int time; // 시간

        public Emoticon(int countOnScreen, int countOnClipboard, int time) {
            this.countOnScreen = countOnScreen;
            this.countOnClipboard = countOnClipboard;
            this.time = time;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        target = sc.nextInt();
        System.out.println(bfs());
    }

    public static int bfs() {
        Queue<Emoticon> q = new LinkedList<>();
        q.add(new Emoticon(1, 0, 0));
        isVisited[1][0] = true;
        while (!q.isEmpty()) {
            Emoticon cur = q.poll();
            int countOnScreen = cur.countOnScreen;
            int countOnClipboard = cur.countOnClipboard;
            int time = cur.time;
            if(countOnScreen == target){
                return time;
            }
            if(countOnScreen > 0 && countOnScreen < 1001){
                // 화면에 있는 이모티콘 클립보드에 저장
                if(!isVisited[countOnScreen][countOnScreen]){
                    q.add(new Emoticon(countOnScreen, countOnScreen, time + 1));
                    isVisited[countOnScreen][countOnScreen] = true;
                }
                // 화면에 있는 이모티콘 한개 삭제
                if(!isVisited[countOnScreen-1][countOnClipboard]){
                    q.add(new Emoticon(countOnScreen - 1, countOnClipboard, time + 1));
                    isVisited[countOnScreen - 1][countOnClipboard] = true;
                }
            }
            if(countOnClipboard != 0){
                //클립보드에 있는 모든 이모티콘 붙여넣기
                if(!isVisited[countOnScreen+countOnClipboard][countOnClipboard]){
                    q.add(new Emoticon(countOnScreen + countOnClipboard, countOnClipboard, time + 1));
                    isVisited[countOnScreen + countOnClipboard][countOnClipboard] = true;
                }
            }
        }
        return -1;
    }
}