백준 14226 이모티콘 C++ 풀이 (BFS)

안녕하세요 여러분~~~~~~~~

프루니입니다 !!

 

오늘 풀어볼 문제는 백준 14226 이모티콘 문제입니다~

언어는 C++입니다.

 

 

---

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

---

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

---

문제풀이

먼저 해야할 일을 정리해볼게요!

문제에서 제시한 가능한 연산 3가지는 복사, 붙여넣기, 한개 지우기에요!

또한 시간의 "최솟값"을 구하는 것이기 때문에 BFS를 사용해야해요

 

연산을 하나씩 살펴볼게요

각 연산 직전 임티개수와 클립보드의 임티개수를 ImojiNum, CopyNum이라고 해볼게요

그럼 각 연산을 해보면! (임티개수, 클립보드 임티개수)

- 복사 : (ImojiNum, CopyNum) -> ( ImojiNum , ImojiNum ) 

----> 현재 임티개수에는 변함이 없고 현재 임티 개수가 그대로 클립보드 임티개수가 됩니다.

 

- 붙여넣기 : (ImojiNum, CopyNum) -> (ImojiNum + CopyNum, CopyNum)

----> 현재 임티개수는 원래 임티개수에 클립보드 임티 개수를 더한 값이 되고 클립보드의 임티개수에는 변함이 없습니다.

 

- 한개 지우기 : (ImojiNum, CopyNum) -> ( ImojiNum - 1, CopyNum)

----> 현재 임티개수는 원래 임티개수에서 1을 빼주면 되고 클립보드의 임티개수에는 변함이 없습니다.

 

 

1. 이모티콘 개수, 카피된 개수를 각각 변수로 잡아줘요

2. 복사, 붙여넣기, 한개 지우기 연산을 각각 적용한 새로운 이모티콘개수, 복사된 개수를 큐에 넣고 연산을 반복해요

3. 큐에서 현재 검사하는 이모티콘개수가 입력받는 S와 같으면 바로 해당 배열의 값(경과 시간)을 리턴해요

 

이렇게 3단계를 거치면 답이 나온답니다!

 

그럼 코드로 구현해볼게요~

 

#include <iostream>
#include <queue>

using namespace std;

int S;
int visited[1001][1001];

int BFS(int imojiNum, int copyNum)
{
    queue<pair<int, int>> q;
    q.push(make_pair(imojiNum, copyNum));
    visited[imojiNum][copyNum] = 1;

    while (!q.empty())
    {
        pair<int, int> front = q.front();
        q.pop();

        if (front.first == S)
        {
            return visited[front.first][front.second];
        }

        int calImojiNum[3] = { front.first, front.first + front.second, front.first - 1 };
        int calCopyNum[3] = { front.first, front.second, front.second };

        for (int i = 0; i < 3; ++i)
        {
            int newImojiNum = calImojiNum[i];
            int newCopyNum = calCopyNum[i];
            
            if (newImojiNum < 0 || newImojiNum > 1000 || newCopyNum < 0 || newCopyNum > 1000)
            {
                continue;
            }

            if (!visited[newImojiNum][newCopyNum])
            {
                visited[newImojiNum][newCopyNum] = visited[front.first][front.second] + 1;
                q.push(make_pair(newImojiNum, newCopyNum));
            }
            
        }
    }
}

int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);

    cin >> S;

    int res = BFS(1, 0);
    cout << --res << '\n'; // 1을 빼는 이유는 문제에서 이미 1개의 이모티콘을 입력한 상태로 시작했기때문이에요!

    return 0;
}

 

여러분 고생많으셨어요!!

도움이 되셨다면 공감버튼 한번씩 눌러주시구 또 방문 부탁드려요!!!

질문이 있으시다면 댓글로 달아주세요! 최대한 빠르게 달려갑니다~

혹시 풀이에서 잘못된 점이나 필요한 개선점을 발견하셨다면 알려주시면 넘넘 감사드리겠습니다!!

도와주세요 선생님들!!!

 

그럼 저는 다음 문제를 또 가지고올게요~~

알고리즘 마스터를 향해서!!

안녕~~~~~~~~~~