[백준] 이모티콘 / JAVA

풀이

bfs탐색을 하면서 1,2,3번 조건을 추가하며 최종 S에 도달할 때 까지 진행한다.
check[][]를 통해 해당 값의 clip에 복사되었던 적이 있었는지 체크하면서 중복을 제거한다.

풀고 나니 간단한 bfs였지만 문제를 푸는 동안에 방문처리를 어떻게 해야되는지 생각이 안나서 3번 이모티콘 갯수를 복사한 값의 절반까지 진행하는 등 이상한 조건을 쓰는 등 헛수고를 오래 하다가 풀게 되었다.

코드

public class BOJ_14226_이모티콘 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static class Node{
        int cnt;
        int num;
        int clip;
        Node(int cnt, int num , int clip){
            this.cnt = cnt;
            this.num = num;
            this.clip = clip;
        }
    }
    public static void main(String[] args) throws IOException {
    
        int result = Integer.parseInt(br.readLine());
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0,1,0));
        boolean checked[][] =new boolean[10001][10001];
        
        while (!q.isEmpty()){
            Node now = q.poll();
            if(checked[now.num][now.clip]){
                continue;
            }
            checked[now.num][now.clip] = true;

            if(now.num == result){
                System.out.println(now.cnt);
                return;
            }

            if(now.clip != now.num) {
                q.add(new Node(now.cnt+1, now.num, now.num ));
            }
            if(now.clip != 0) {
                q.add(new Node(now.cnt+1, now.num + now.clip, now.clip));
            }
            if(now.clip/2 < now.num) {
                q.add(new Node(now.cnt+1, now.num -1, now.clip));
            }

        }



    }

}