[백준 14226]이모티콘

생각 정리

탐색할 수 있는 것 : 3가지 연산
1. 화면에 있는 이모티콘 복사해서 클립보드에 저장 => 이전 내용은 덮어진다.
2. 클립보드에 있는 이모티콘 화면에 붙여넣기
3. 화면에 있는 이모티콘 하나 삭제

• 화면에 이미 1개 있고, 3가지 연산만 사용해서 이모티콘 S개를 만들어야 한다.

클립보드에 있는 이모티콘 개수도 세어야하고,
화면에 있는 이모티콘 개수도 세어야할 것 같다

1. 초기값 : 화면에 1개, 클립보드 0개
   -> 화면 복사 클립보드 저장 : 화면 1개, 클립보드 1개
   -> 클립보드꺼 화면에 붙여넣기 : 화면 1개, 클립보드 0개
   -> 화면 삭제 : 화면 0개, 클립보드 0개

화면 이모티콘 개수와 클립보드 이모티콘 개수, 그리고 시간(?)를 나타내는 class 만들어서 queue에 저장하기
queue에서 빼서 첫번째 연산하면 => 화면 그대로, 클립보드 : 화면 이모티콘 개수 , 시간+1
두번째 연산하면 => 화면 += 클립보드, 클립보드 그대로, 시간+1
세번째 연산 => 화면 -= 1, 클립보드 그대로, 시간+1

화면의 이모티콘 개수가 S개랑 같아지면, 그때의 시간을 출력하기

생각하지 못한 것

화면의 이모티콘 개수, 클립보드의 개수를 통해 방문여부를 점검하기

코드

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

class Emoticon {
    int screen; //화면에 있는 이모티콘 개수
    int board; //클립보드에 있는 이모티콘 개수
    int time; //현재까지의 시간

    Emoticon(int screen, int board, int time) {
        this.screen = screen;
        this.board = board;
        this.time = time;
    }
}

public class Main{
    static int S;
    static boolean[][] visited;
    static Queue<Emoticon> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = Integer.parseInt(br.readLine());
    
        visited = new boolean[10000][10000];
        queue.add(new Emoticon(1, 0, 0));
        visited[1][0] = true;
        bfs();

    }
    
    static void bfs() {

        while(!queue.isEmpty()) {
            Emoticon out = queue.poll();

            if(out.screen == S){
                System.out.println(out.time);
                return ;
            }

            if(out.screen > 0 && !visited[out.screen][out.screen]){
                
                queue.add(new Emoticon(out.screen, out.screen, out.time+1));
                visited[out.screen][out.screen] = true;
            }   
            if(out.board > 0 && !visited[out.screen + out.board][out.board]){
                queue.add(new Emoticon(out.screen + out.board, out.board, out.time+1));
                visited[out.screen + out.board][out.board] = true;
            }
            if(out.screen > 0 && !visited[out.screen -1][out.board]){
                queue.add(new Emoticon(out.screen-1, out.board, out.time+1));
                visited[out.screen -1][out.board] = true;
            }

        }
    }
}