[BaekJoon] 14226번 - 이모티콘 [Java][C++]

문제 링크

---

1. 문제 풀이

이모티콘 $S$ 개를 만드는 과정은 BFS를 활용하면 해결할 수 있다. 탐색은 현재 화면에 있는 이모티콘 수와 클립보드에 있는 이모티콘 수가 모두 필요하므로 두 가지 파라미터를 갖는 객체를 활용해 3가지 연산을 적용하며 BFS를 돌려줬다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MAX = 1000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int s = Integer.parseInt(br.readLine());
        System.out.println(bfs(s));
    }

    static int bfs(int s) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{1, 0});

        boolean[][] visited = new boolean[1 + MAX][1 + MAX];
        visited[1][0] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int[] node = q.poll();
                if (node[0] == s) return dist;

                if (!visited[node[0]][node[0]]) {
                    q.offer(new int[]{node[0], node[0]});
                    visited[node[0]][node[0]] = true;
                }

                if (node[0] + node[1] <= MAX && !visited[node[0] + node[1]][node[1]]) {
                    q.offer(new int[]{node[0] + node[1], node[1]});
                    visited[node[0] + node[1]][node[1]] = true;
                }

                if (node[0] > 0 && !visited[node[0] - 1][node[1]]) {
                    q.offer(new int[]{node[0] - 1, node[1]});
                    visited[node[0] - 1][node[1]] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 1000;
bool visited[1 + MAX][1 + MAX];

int bfs(int s) {
    queue<pair<int, int>> q;
    q.push({1, 0});

    visited[1][0] = true;

    int dist = 0;

    while (!q.empty()) {
        int size = q.size();

        while (size-- > 0) {
            auto [a, b] = q.front();
            q.pop();

            if (a == s) return dist;

            if (!visited[a][a]) {
                q.push({a, a});
                visited[a][a] = true;
            }

            if (a + b <= MAX && !visited[a + b][b]) {
                q.push({a + b, b});
                visited[a + b][b] = true;
            }

            if (a > 0 && !visited[a - 1][b]) {
                q.push({a - 1, b});
                visited[a - 1][b] = true;
            }
        }

        dist++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int s;
    cin >> s;
    cout << bfs(s);
}

---