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

백준의 이모티콘(14226) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 문제의 조건에 맞게 BFS를 구현해야 하는 문제이다. 문제의 조건에 대해서 다시 한번 확인해보자.

   그리고 현재의 상태는 화면에 이모티콘이 1개가 입력되어 있는 상태이다.

2. 일반적인 BFS를 구현할 때에, 해당 정점을 이미 방문했는지 안했는지를 판단해야 하는 과정이 필요하다.

   본인은 이 문제에서 해당 정점을 (x,y)가 아닌 (화면, 클립보드)로 두어서 이를 관리할 수 있는 2차원 Visit[][] 배열을

   사용하였다.

   즉, Visit[a][b]의 의미는 " 화면에 a개의 이모티콘이 있고, 클립보드에 b개의 이모티콘이 있는 상태 " 를 의미하고

   저 배열의 값이 true냐, false냐에 따라서 이미 탐색 했는지 안했는지를 결정하는 것이다.

 

   마찬가지로, BFS의 Queue를 (화면의 이모티콘 갯수, 클립보드의 이모티콘 갯수) 이렇게 한 쌍과, 답을 도출해내기 위해

   시간을 나타내는 int형 한개를 추가해서 총 3개의 변수값을 관리해 주었다.

   문제의 조건에 맞게, 처음에는 화면에 1개의 이모티콘이 입력되어 있는 상태라고 했으므로

   Q.push({ 1, 0} , 0)으로 초기 상태를 설정해 주었다. 또한 Visit[1][0] = true로 설정해주었다.

   < 앞에 1 = 화면에 있는 1개의 이모티콘, 가운데 0 = 클립보드의 이모티콘 갯수, 뒤에 0 = 시간 >

3. 이제 조건에 맞게 BFS를 실행시켜 주면 되는데, 조건에 대해서 생각해보자.

   < 1번 조건 > - 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.

   - 이 조건을 실행시키기 위해서는 조건이 필요하다. 화면에 있는 이모티콘을 모두 복사한다고 하였으니, 화면에 있는

     이모티콘의 갯수가 1개 이상이어야 한다.

   - 이 조건을 실행시키게 되면, 화면과 클립보드에 있는 이모티콘의 갯수는 (화면의 이모티콘 갯수, 화면의 이모티콘 갯수)

     가 될 것이다. 왜냐하면,

    

     이 조건 때문이다. 클립보드에 화면에 있는 내용을 복사해서 저장하게 되면, 클립보드에 몇개의 이모티콘이 있었던지

     상관 없이 덮어쓰기가 되므로, 화면의 이모티콘 갯수가 그대로 클립보드로 저장되어지게 된다.

   < 2번 조건 > - 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.

   - 이 조건을 실행시키기 위한 조건으로는, 클립보드에 이모티콘의 갯수가 1개 이상이어야 한다라는 것이다.

   - 이 조건을 실행하게 되면, 화면과 클립보드에 있는 이모티콘의 갯수는

     ( 기존의 화면의 이모티콘 갯수 + 클립보드의 이모티콘 갯수 , 클립보드의 이모티콘 갯수) 가 될 것이다.

     즉, 화면에는 기존의 상태에서 클립보드의 이모티콘 갯수만큼 추가가 되는 것이고, 클립보드에는 변동이 없다.

   < 3번 조건 > - 화면에 있는 이모티콘 중 하나를 삭제한다.

   - 이 조건을 실행시키기 위해서는, 화면에 있는 이모티콘이 1개 이상이어야 한다.

   - 이 조건을 실행시키기 되면, 화면과 클립보드의 이모티콘 갯수는 (화면의 이모티콘 갯수 -1, 클립보드의 이모티콘 갯수) 가

     된다.

위의 조건들에 알맞게 코드를 잘 구현한다면 어렵지 않은 문제가 될 것이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 2000
using namespace std;
 
int S;
bool Visit[MAX][MAX];
 
void Input()
{
    cin >> S;
}
 
int BFS()
{
    queue<pair<pair<int, int>, int> > Q;
    Q.push(make_pair(make_pair(1, 0), 0));
    Visit[1][0] = true;    // 화면, 클립보드
 
    while (Q.empty() == 0)
    {
        int Dis = Q.front().first.first;
        int Clip = Q.front().first.second;
        int Time = Q.front().second;
        Q.pop();
 
        if (Dis == S) return Time;
        
        if (Dis > 0 && Dis < MAX)
        {
            //1번 & 3번 조건
            if (Visit[Dis][Dis] == false)
            {
                Visit[Dis][Dis] = true;
                Q.push(make_pair(make_pair(Dis, Dis), Time + 1));
            }
 
            if (Visit[Dis - 1][Clip] == false)
            {
                Visit[Dis - 1][Clip] = true;
                Q.push(make_pair(make_pair(Dis - 1, Clip), Time + 1));
            }
        }
 
        if (Clip > 0 && Dis+Clip < MAX)
        {
            if (Visit[Dis + Clip][Clip] == false)
            {
                Visit[Dis + Clip][Clip] = true;
                Q.push(make_pair(make_pair(Dis + Clip, Clip), Time + 1));
            }
        }
    }
}
 
 
void Solution()
{
    int R = BFS();
    cout << R << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}