알고리즘41 :: BOJ_14226_이모티콘

package backjun;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
 
public class backjun_14226_이모티콘 {
 
    private static int time = Integer.MAX_VALUE;
    private static boolean[][] visit;
    private static int goal = 0;
    private static int BFS(int goal) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {1,0,0}); //화면, 클립보드, 시간 
        while(!q.isEmpty()) {
            int[] p = q.remove();
            
            if(goal == p[0]) {
                time = p[2];
                return time;
            }
            
            if(p[0]>1000 || p[1]>1000) continue;
            if(visit[p[0]][p[1]]==false && p[0]>=1) { //클립 보드 복사 어떻게? 
                q.add(new int[] {p[0],p[0],p[2]+1});
                q.add(new int[] {p[0]-1,p[1],p[2]+1});
            }
            
            if(visit[p[0]][p[1]]==false && p[1]>=1) {
                q.add(new int[] {p[0]+p[1],p[1],p[2]+1});
            }
            visit[p[0]][p[1]] = true;
        }
        return time;
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        goal = Integer.parseInt(br.readLine());
        visit = new boolean[1001][1001];
        System.out.println(BFS(goal));
    }
 
}
 

이모티콘 문제에서 얍문님 블로그를 참고했다.

화면에 보이는 수 = p[0] / 클립보드에 복사된 수 = p[1]  가 이중 배열로 visit 체크 해서 stack over flow를 방지했다. 

처음에 생각했던것은 단순히 숫자만 방문체크 해줄려 했는데 잘 안풀렸다. 두가지를 신경쓰지 못한것이 이 문제를 풀지 못했던 이유가 아닐까 싶다. 

 

프로세싱은 크게 3가지 = 복사(클립보드로, 덮어쓰기 상관없음)/ 붙여넣기(화면으로 복사)/ 삭제(하나 차감)

복사 = 화면에 하나 이상 있어야 한다. p[0] >=1

붙여넣기 = 클립보드에 하나 이상 있어야 한다. p[1] >=1

삭제 = 화면에 하나 이상 있어야 한다. p[0]>=1