백준 14226. 이모티콘 :: 돼지개발자

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

"BFS, visited 배열을 잘 생각하자.."

해당 문제를 풀다가 visited[] 배열을 어디까지 할까 고민하다.... 1001 로 해서 런타임 에러, 2002 로 했더니 틀렸다.... 

잘 생각해보니 특정 이모티콘 길이에 도착했을 때, 버퍼에 1글자를 가지고 오는것과 10글자를 가지고 오는 것은 다른 경우...

따라서 이차원 배열을 방문체크 배열로 해야한다.

visited[이모티콘길이][버퍼의길이]

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    
    static int S;
    static boolean[][] visited = new boolean[2002][2002];
    static Queue<Node> q = new LinkedList<>();
    static int min;
    
    public static void main(String[] args) throws IOException {
        
        Scanner sc = new Scanner(System.in);
        
        S = sc.nextInt();    
        
        visited[1][0] = true;
        q.add(new Node(1, 0, 0));
        
        while(!q.isEmpty()) {
            
            Node cur = q.poll();
            
            if(cur.len == S) {
                min = cur.cnt;
                break;
            }
            
            // copy
            q.add(new Node(cur.len, cur.len, cur.cnt+1));
            
            // paste
            if(cur.buf != 0 && !visited[cur.len+cur.buf][cur.buf] && cur.len+cur.buf <= 1000) {
                visited[cur.len+cur.buf][cur.buf] = true;
                q.add(new Node(cur.len+cur.buf, cur.buf, cur.cnt+1));    
            }
            
            // delete
            if(cur.len > 0 && !visited[cur.len-1][cur.buf] && cur.len-1 <= 1000) {
                visited[cur.len-1][cur.buf] = true;
                q.add(new Node(cur.len-1, cur.buf, cur.cnt+1));    
            }
        }
        System.out.println(min);
    }
    
}
 
class Node {
    int len;
    int buf;
    int cnt;
    Node ( int len, int buf, int cnt) {
        this.len = len;
        this.buf = buf;
        this.cnt = cnt;
    }
    
}