백준 14226 (이모티콘) - java

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

14226번: 이모티콘

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

public class Main {
    static int n= 0;
    static int result = 0;
    static boolean[][] visit = new boolean[1002][1002]; // 행 : 이모티콘 개수 , 열 : 클립의 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        bfs();
        System.out.println(result);
        br.close();
    }

    static void bfs()
    {
        Queue<point> q =new LinkedList<>();
        q.add(new point(1,0,0)); // 차례대로 이모티콘 개수 / 클립 개수 / 시간
        visit[1][0] = true; // 1 , 0 에서 시작
        while(!q.isEmpty())
        {
            point cur = q.poll();
            if(cur.num==n)
            {
                if(result==0)
                    result = cur.time;
                else if(result>cur.time)
                {
                    result = cur.time;
                }
            } // 최솟값을 구하는 문제
            for(int i=0;i<3;i++)
            {
                if(i==0) // 클립보드에 현재 이모티콘의 개수만큼 저장하는 경우
                {
                    if(!visit[cur.num][cur.num])
                    {
                        visit[cur.num][cur.num] = true;
                        q.add(new point(cur.num,cur.num, cur.time+1));
                    }
                }

                if(i==1 && cur.num+cur.clip<=n+1) // 클립보드의 이모티콘들을 전부 붙혀넣는 경우 
                {
                    if(!visit[cur.num+cur.clip][cur.clip])
                    {
                        visit[cur.num+cur.clip][cur.clip] = true;
                        q.add(new point(cur.num+cur.clip,cur.clip,cur.time+1));
                    }
                }

                if(i==2&&cur.num>=1) // 이모티콘들 중 한개를 삭제하는 경우
                {
                    if(!visit[cur.num-1][cur.clip])
                    {
                        visit[cur.num-1][cur.clip] = true;
                        q.add(new point(cur.num-1,cur.clip,cur.time+1));
                    }
                }
            }
        }
    }
}
class point
{
    int num;
    int clip;
    int time;

    point(int num,int clip,int time)
    {
        this.num = num;
        this.clip = clip;
        this.time= time;
    }
}

해당 경우에 있어 조건식을 한번 살펴 볼 필요가 있다. 손으로 몇 개 돌려보면 알겠지만 주어진 n개에 대하여 해당 값이 나오는 경우는 최대 n+1개에서 3번째 연산으로 1개를 빼는 경우이다. 

이 조건을 파악하지 않을 경우 불필요한 연산의 수가 너무 많아지거나 index 에러를 보게 될 것이다....