14226 - 이모티콘

2차원 탐색 문제이다.
다른 탐색 문제들과는 조금 다른 점이 있는데, 클립보드에 어떤 값이 저장되어있냐에 따라서 다음 정점이 달라진다는 것이다.
문제에서 나와있는 분기의 종류가 3가지이기 때문에 한 정점에서 3개의 간선이 뻗어나간다고 생각 할 수 있는데, 이것은 틀린 생각이다.
1번째 2번째 분기는, 클립보드에 저장된 수에 따라서 각각 간선이 있다고 생각한 후 문제를 풀어야한다. 그래서 2차원 배열로 두고 풀면 쉽게 풀렸던 문제였다.
vertex(이모티콘의 개수), clip(클립보드에 저장된 이모티콘의 개수) 두 값을 가지고 있는 클래스를 선언해준 후, 각각의 경우에 따라 분기를 돌 수 있도록 bfs를 이용해 문제를 풀이했다.
MAX값이 2000인 이유는, S의 범위가 1000이고(아래 코드에서는 vertex) + 클립보드에 저장될 이모티콘의 개수는 S의 범위와 일치
하므로, 최댓값이 2000정도 나온다고 생각하여 문제를 풀이했다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

class Vnc {
    int vertex;
    int clip;
    Vnc (int vertex, int clip) {
        this.vertex = vertex;
        this.clip = clip;
    }
}

public class Main {
    static int MAX = 2000;

    public static void bfs(int[][] map, boolean[][] visited) {
        Queue<Vnc> q = new LinkedList<>();
        q.add(new Vnc(1, 0));
        visited[1][0] = true;
        while (!q.isEmpty()) {
            Vnc cur = q.poll();
            int v = cur.vertex;
            int c = cur.clip;
            if (!visited[v][v]) {
                visited[v][v] = true;
                q.add(new Vnc(v, v));
                map[v][v] = map[v][c] + 1;
            }
            if (v + c < MAX) {
                if (!visited[v + c][c]) {
                    visited[v + c][c] = true;
                    q.add(new Vnc(v + c, c));
                    map[v + c][c] = map[v][c] + 1;
                }
            }
            if (v - 1 >= 0) {
                if (!visited[v - 1][c]) {
                    visited[v - 1][c] = true;
                    q.add(new Vnc(v - 1, c));
                    map[v - 1][c] = map[v][c] + 1;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(br.readLine());
        int[][] map = new int[MAX][MAX];
        boolean[][] visited = new boolean[MAX][MAX];
        bfs(map, visited);
        int min = 2147483647;
        for (int i = 0; i < map[S].length; i++) {
            if (min > map[S][i] && visited[S][i]) min = map[S][i];
        }
        System.out.println(min);
    }
}