[백준] 14226번 이모티콘

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

14226번: 이모티콘

화면에있는이모티콘수, 클립보드에 있는 이모티콘수 를 이차원 배열로 상태관리

 

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

public class Main {

    static int max = 1001;
    static int S;
    static boolean[][] visit = new boolean[max][max];

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        int result = bfs(S);
        System.out.println(result);
	}

    public static int bfs(int s) {
        Queue<Emo> q = new LinkedList<>();
        q.offer(new Emo(1, 0, 0));
        // 화면갯수, 클립보드 갯수
        visit[1][0] = true;
        int retVal = -1;

        while (!q.isEmpty()) {
            Emo curEmo = q.poll();
            int scrCount = curEmo.getScrCount();
            int clipCount = curEmo.getClipCount();
            int time = curEmo.getTime();

            if (s == scrCount) {
                retVal = time;
                break;
            }

            if (scrCount > 0 && scrCount < max) {
                // 화면에 있는 이모티콘 복사 후 클립보드 저장
                if (!visit[scrCount][scrCount]) {
                    visit[scrCount][scrCount] = true;
                    q.offer(new Emo(scrCount, scrCount, time + 1));
                }
                // 클립보드에 있는 이모티콘 복사 후 화면에 플러스
                if (clipCount > 0 && (scrCount + clipCount) < max) {
                    if (!visit[scrCount + clipCount][clipCount]) {
                        visit[scrCount + clipCount][clipCount] = true;
                        q.offer(new Emo(scrCount + clipCount, clipCount, time + 1));
                    }
                }
                // 화면에서 1개 삭제
                if (!visit[scrCount - 1][clipCount]) {
                	visit[scrCount - 1][clipCount] = true;
                	q.offer(new Emo(scrCount-1 , clipCount, time + 1));
                }
            }

        }
        return retVal;
    }

    private static class Emo {
        int scrCount;
        int clipCount;
        int time;

        public Emo(int scrCount, int clipCount, int time) {
            this.scrCount = scrCount;
            this.clipCount = clipCount;
            this.time = time;
        }

        public int getScrCount() {
        	return scrCount;
        }

        public int getClipCount() {
        	return clipCount;
        }

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