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

출처 : 14226번: 이모티콘 (acmicpc.net)

14226번: 이모티콘

풀이 방법

bfs를 이용 시 동일 단위크기로 나누는 것이 중요하다 처음에는 queue에 화면에서 이모티콘 하나를 삭제하는 경우 time + 1인 경우와 화면에서 클립에 복사하고 클립에서 다시 화면으로 복사하는 경우 time + 2로 나누었는데 

이렇게 하면 time의 크기가 달라져 복잡해진다. 그리고 항상 클립과 화면의 이모티콘의 개수가 똑같아진다는 오류도 생긴다 

그러므로

1. 화면에서 이모티콘 하나를 삭제하는 경우

2. 화면에서 클립으로 이모티콘을 복사하는 경우

3. 클립에서 화면으로 이모티콘을 붙여넣기 하는 경우

세 가지로 나누어 queue에 저장한다.

visited는 화면에 있는 [이모티콘 개수][클립의 이모티콘 개수]로 같은 경우에 대해서 두 번 처리하지 않도록 한다.

queue에는 스크린 이모티콘 개수 , 클립의 이모티콘 개수, 시간을 넣어 준다.

#include <bits/stdc++.h>
using namespace std ;

int S, ans;
int visited[1001][1001];

int bfs() {

    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(1, 0), 0));

    while(!q.empty()) {
        int screen = q.front().first.first;
        int clip = q.front().first.second;
        int time = q.front().second;
        q.pop();
        if (screen == S) return time;
        // 클립 복사
        if (screen > 0 && screen < 1001) {
            if (visited[screen][screen] == -1) {
                visited[screen][screen] = 1;
                q.push(make_pair(make_pair(screen, screen), time + 1));
            }
        }
        // 클립 에서 화면에 복사
        if (clip > 0 && screen + clip < 1001) {
            if (visited[screen + clip][clip] == -1) {
                visited[screen + clip][clip] = 1;
                q.push(make_pair(make_pair(screen + clip, clip), time + 1));
            }
        }
        // 화면에서 하나 삭제
        if (screen - 1 > 0) {
            if (visited[screen - 1][clip] == -1) {
                visited[screen - 1][clip] = 1;
                q.push(make_pair(make_pair(screen - 1, clip), time + 1));
            }
        }
    }
}


int main () {

    memset(visited, -1, sizeof(visited));
    cin >> S;
    ans = bfs();
    cout << ans;
    return 0;
}