[백준/C++] 14226번: 이모티콘

문제 & 링크

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

풀이

1. 걸리는 시간의 최솟값을 구하기 위해서 BFS를 사용한다.

2. 화면에 있는 이모티콘의 개수, 클립보드에 있는 이모티콘의 개수가 BFS의 큐에 저장이 되어야 하며, 시간을 구하기 위해 시간도 저장해준다.

3. 문제의 3가지의 연산에 대해서 BFS를 실행해준다. 이때 visited 배열로 방문 여부를 확인하지 않으면 3의 제곱 형태로 시간초과가 나올 수 있다.

4. visited 배열의 범위를 벗어나지 않게 하기 위해 2번 연산, 3번 연산에서 범위를 조정해준다.

코드

#include <iostream>
#include <queue>

using namespace std;

bool visited[1001][1001]; // 방문 여부, 화면 이모티콘 개수 & 클립보드 이모티콘 개수

int main() {
    int S;
    cin >> S;

    queue<pair<pair<int, int>, int>> q; // 화면 이모티콘 개수, 클립보드 이모티콘 개수, 시간
    visited[1][0] = true;
    q.push({ {1, 0}, 0 });

    while (!q.empty()) {
        int emoticon_num = q.front().first.first; // 화면 이모티콘 개수
        int clipboard_num = q.front().first.second; // 클립보드 이모티콘 개수
        int time = q.front().second; // 시간
        q.pop();

        if (emoticon_num == S) { 
            cout << time;
            break;
        }
        
        // 1번 연산
        if (!visited[emoticon_num][emoticon_num]) { 
            visited[emoticon_num][emoticon_num] = true;
            q.push({ {emoticon_num, emoticon_num}, time + 1 });
        }
        // 2번 연산
        if (emoticon_num + clipboard_num <= 1000 && !visited[emoticon_num + clipboard_num][clipboard_num]) {
            visited[emoticon_num + clipboard_num][clipboard_num] = true;
            q.push({ {emoticon_num + clipboard_num, clipboard_num}, time + 1 });
        }
        // 3번 연산
        if (emoticon_num - 1 > 0 && !visited[emoticon_num - 1][clipboard_num]) {
            visited[emoticon_num - 1][clipboard_num] = true;
            q.push({ {emoticon_num - 1, clipboard_num}, time + 1 });
        }
    }
}