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

문제링크 : www.acmicpc.net/problem/14226

14226번: 이모티콘

3가지 연산에 대해서 비용이 모두 1이다. S가 1000이하여서 BFS로 해결 되었다.

import java.io.*;
import java.util.*;
public class Main {
	public static boolean visited[][];
	
	public static class Node{
		int emoticon;
		int copyCnt;
		public Node(){}
		public Node(int a, int b){
			emoticon = a;
			copyCnt = b;
		}
	}
	public static void main(String[] args)throws Exception {
		visited = new boolean[1001][1001];

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		Queue<Node> q = new LinkedList<Node>();
		q.add(new Node(1,0));
		int ans = 0;
		exit:while(!q.isEmpty()){
			int qSize = q.size();
			for(int i=0;i<qSize;i++){
				Node cNode = q.poll();
				if(cNode.emoticon == n){
					break exit;
				}
				if(cNode.emoticon > n || cNode.emoticon == 0) continue;
				if(visited[cNode.emoticon][cNode.copyCnt]) continue;
				visited[cNode.emoticon][cNode.copyCnt] = true;
				if(cNode.emoticon != cNode.copyCnt){
					q.offer(new Node(cNode.emoticon,cNode.emoticon));
				}
				if(cNode.copyCnt!=0){
					q.offer(new Node(cNode.emoticon + cNode.copyCnt,cNode.copyCnt));
				}
				q.offer(new Node(cNode.emoticon-1,cNode.copyCnt));
			}
			ans++;
		}
		System.out.println(ans);
	}

}