[백준 14226번] 이모티콘 (C++)

문제링크 : https://www.acmicpc.net/problem/14226

14226번: 이모티콘

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int S;
int arr[1001][1001]; //화면, 클립보드

void bfs()
{
    queue<pii>q;
    q.push({1, 0}); //초기화 상태 (화면에 이모티콘 1개)
    while(!q.empty())
    {
        auto [screen, board] = q.front();
        q.pop();
        if(screen == S) 
        {
            cout << arr[screen][board];
            return;
        }

        if(!arr[screen][screen]) //복사
        {
            arr[screen][screen] = arr[screen][board] + 1;
            q.push({screen, screen});
        }

        if(screen+board < 1001 && !arr[screen+board][board]) //붙여넣기
        {
            arr[screen+board][board] = arr[screen][board] + 1;
            q.push({screen+board, board});
        }

        if(screen > 0 && !arr[screen-1][board]) //삭제
        {
            arr[screen-1][board] = arr[screen][board] + 1;
            q.push({screen-1, board});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> S;
    bfs();
}

 

문제에 주어진 조건을 그대로 차근차근 작성하면 되는 bfs 문제이다.

먼저 방문체크 및 시간을 담을 2차원 배열을 선언한다.

N의 크기에 따라 [1001][1001]로 선언했고 앞이 화면, 뒤가 클립보드를 나타내는 것을 가정한다.

 

큐를 선언하고 값을 넣어주는데, 문제에서 초기상태는 화면에 이모티콘 1개를 입력한 상태라고 하였다.

따라서 큐에 1(화면)과  0(클립보드)을 초기값으로 넣어준다.

이후 큐의 first가 화면, second가 board인 것을 가정한다.

 

먼저 첫 번째 연산인 화면 -> 클립보드 복사 과정이다.

현재 화면의 값(screen)과 클립보드의 값이 같아야 하므로 2차원 배열의 board 위치에 screen의 값을 그대로 넣어준다.

그리고 매 계산마다 시간은 1초가 걸리므로 계산을 행한 후인 arr[screen][screen]의 값에 전 배열의 값 + 1을 저장해주고 큐에 연산한 값을 넣어준다.

모든 연산은 연산을 거친 위치에 값이 없을 시에만 행하도록 해준다. (중복 방지)

 

다음으로 붙여넣기이다.

붙여넣기의 경우 클립보드에 있는 모든 이모티콘을 화면으로 넣는 과정이다.

따라서 화면 = 화면 + 클립보드의 값이 된다는 것을 알 수 있다.

이때 화면의 값이 1001을 넘어간다면 OutOfBound가 발생하므로 1001이 넘어가지 않도록 예외처리를 해주어야 한다.

이외에는 동일하다. (배열 값  1, 큐에 값 넣기)

 

마지막으로 삭제과정이다.

삭제의 경우 화면의 값이 1미만으로 내려가면 안된다.

따라서 예외처리로 화면의 값이 항상 0보다 클때만 삭제과정을 거치도록 해주어야 한다.

이외에는 동일하다. (배열 값  1, 큐에 값 넣기)

 

위 3과정에 걸쳐 시간이 저장되고, 화면과 S가 같아 질때 출력하도록 한다.