[백준] 14226번 : 이모티콘

문제

 

---

풀이

 

클립보드를 관리하는 것이 중요한 문제다.

처음에는 덮어씌워진다길래 변수 하나로 클립보드를 관리하려 했는데, bfs의 상태에 따라 클립보드의 상태가 다를 수도 있다는걸 생각하지 못한 것이다...

 

그래서 방문여부를 관리하는 visited 배열을 2차원 배열로 만들어 클립보드의 정보를 저장했다.

그리고 이모티콘의 현상태 정보또한 구조체로 관리했다. 구조체에는 이모티콘의 개수와 그때까지 걸린 시간, 그리고 그 상태에 클립보드에 복사된 이모티콘의 개수를 저장했다.

---

소스코드

 

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 1001;

struct emoji {
    int num, time, pasted;
};

int S;
bool visited[MAX][MAX]; //visited[num][pasted]

int bfs() {
    queue<emoji> q;

    q.push({1, 0, 0});
    visited[1][0] = true;
    while (!q.empty()) {
        int c_num = q.front().num; //이모티콘 수
        int c_time = q.front().time; //걸린 시간
        int c_pasted = q.front().pasted; //클립보드에 복사된 이모티콘 수
        q.pop();
        if (c_num == S) //종료 조건
            return c_time;

        if ((c_num > 0) && !visited[c_num][c_num]) { //클립보드 복사
            visited[c_num][c_num] = true;
            q.push({c_num, c_time + 1, c_num});
        }
        if (((c_num + c_pasted) < MAX) && !visited[c_num + c_pasted][c_pasted]) { //붙여넣기
            visited[c_num + c_pasted][c_pasted] = true;
            q.push({c_num + c_pasted, c_time + 1, c_pasted});
        }
        if ((c_num > 0) && !visited[c_num - 1][c_pasted]) { //삭제
            visited[c_num - 1][c_pasted] = true;
            q.push({c_num - 1, c_time + 1, c_pasted});
        }
    }
    return 0;
}

int main() {
    cin >> S;
    cout << bfs();
}

전체 소스코드다.

 

struct emoji {
    int num, time, pasted;
};

int S;
bool visited[MAX][MAX]; //visited[num][pasted]

이모티콘의 정보를 저장할 구조체와 클립보드를 저장하기 위해 2차원 배열로 선언한 visited이다.

 

    q.push({1, 0, 0});
    visited[1][0] = true;

초기 상태에서 이모티콘 1개, 걸린 시간은 0초, 클립보드에 복사된 이모티콘의 개수는 0개이다.

그 정보대로 큐에 넣어주고 방문 처리를 한다.

 

        int c_num = q.front().num; //이모티콘 수
        int c_time = q.front().time; //걸린 시간
        int c_pasted = q.front().pasted; //클립보드에 복사된 이모티콘 수
        q.pop();
        if (c_num == S) //종료 조건
            return c_time;

종료 조건은 이모티콘의 수를 나타내는 c_num이 목표 개수인 S와 일치할 떄이다.

 

        if ((c_num > 0) && !visited[c_num][c_num]) { //클립보드 복사
            visited[c_num][c_num] = true;
            q.push({c_num, c_time + 1, c_num});

클립보드에 복사를 하기 위해선 당연히 현재 이모티콘의 수가 1개 이상이어야 할 것이다.

그리고 만약 이미 해당 이모티콘을 클립보드에 복사했었다면 visited[c_num][c_num]이 true일 것이다.

 

조건을 통과하면 visited[c_num][c_num]을 true로 하고 c_time과 c_pasted 값을 변경하여 큐에 넣는다.

 

        if (((c_num + c_pasted) < MAX) && !visited[c_num + c_pasted][c_pasted]) { //붙여넣기
            visited[c_num + c_pasted][c_pasted] = true;
            q.push({c_num + c_pasted, c_time + 1, c_pasted});
        }
        if ((c_num > 0) && !visited[c_num - 1][c_pasted]) { //삭제
            visited[c_num - 1][c_pasted] = true;
            q.push({c_num - 1, c_time + 1, c_pasted});
        }

클립보드에 붙여넣기를 하려면 일단 붙여넣기 한 뒤의 c_num 값이 MAX를 넘어선 안될 것이다.

그리고 삭제를 하기 위해선 이모티콘의 개수가 1개 이상이어야 한다.

 

방문 조건도 확인한뒤, 조건을 통과하면 c_num과 c_time 값을 변경하여 큐에 넣는다.