백준 14226 이모티콘 (Java)

1. 문제 링크

14226번: 이모티콘

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 최소 시간을 구하는 문제라 BFS 탐색을 이용했다.
2. 큐에 지금 이모티콘 수(now), 클립보드에 있는 이모티콘 수(save), 연산 횟수(cnt) 3가지를 넣는다.
3. 원하는 이모티콘 수가 나올 때까지 반복한다.
    3-1. now가 0보가 크고, [now][now]에 방문한 적이 없는 경우에, 클립보드로 복사한다.
    3-2. save가 0보다 크고, now+save가 2000보다 작고, [now+save][save]에 방문한 적이 없는 경우에, 클립보드에 있는 이모티콘을 붙여넣는다.
    3-3. now가 0보다 크고, [now-1][save]에 방문한 적이 없다면, 이모티콘을 하나 지운다. 

 

4. 코드

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        //S개를 만드는 최솟값 => BFS 탐색

        boolean[][] visit = new boolean[2001][2001];
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{1, 0, 0}); //지금 이모티콘 수, 클립보드 이모티콘 수, 연산 횟수
        visit[1][0] = true;

        int result = 0;
        while (!q.isEmpty()) {
            int[] current = q.poll();
            int now = current[0];
            int save = current[1];
            int cnt = current[2];

            if (now == S) {
                result = cnt;
                break;
            }

            //1번
            if (now > 0 && !visit[now][now]) {
                q.offer(new int[]{now, now, cnt + 1});
                visit[now][now] = true;
            }

            //2번
            if (save > 0 && now+save <2000 && !visit[now + save][save]) {
                q.offer(new int[]{now + save, save, cnt + 1});
                visit[now + save][save] = true;
            }

            //3번
            if (now > 0 && !visit[now - 1][save]) {
                q.offer(new int[]{now - 1, save, cnt + 1});
                visit[now - 1][save] = true;
            }
        }

        System.out.println(result);
    }
}