[백준] 14226 이모티콘 - JAVA

1. 문제유형 : BFS

2. 시간복잡도 : O(N^2)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static class Node {
		int n;
		int clip;
		int time;

		public Node(int n, int clip, int time) {
			super();
			this.n = n;
			this.clip = clip;
			this.time = time;
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int S = Integer.parseInt(in.readLine());
		Queue<Node> queue = new LinkedList<Node>();
		boolean[][] visited = new boolean[2001][2001];
		queue.add(new Node(1, 0, 0));
		
		while(!queue.isEmpty()) {
			Node current = queue.poll();
			if(current.n == S) {
				System.out.println(current.time);
				break;
			}
			if(visited[current.n][current.clip]) continue;
			visited[current.n][current.clip] = true;
			// 복사
			if(current.n != current.clip && current.n <= 2000) {
				queue.add(new Node(current.n, current.n, current.time+1));
			}
			// 붙여넣기
			if(current.clip != 0 && current.n + current.clip <= 2000) {
				queue.add(new Node(current.n+current.clip, current.clip, current.time+1));
			}
			// 삭제
			if(current.n > 1 && current.n <= 2000) {
				queue.add(new Node(current.n-1, current.clip, current.time+1));
			}
		}
	}

}