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

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

14226번: 이모티콘

전형적인 BFS문제이다. 여기에 누적 시간을 기록하기 위해 약간의 DP 개념을 활용하면 된다.

 

문제에서 사용자가 움직일 수 있는 범위는 크게 3가지로 분류된다. (화면 = sc, 클립보드 = cl)

1. 화면에 있는 이모티콘을 클립보드에 저장 (이때 기존 클립보드에 있는 내용은 모두 날라가고 덮어쓰기 됨)
(sc, cl) -> (sc, sc) 

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기

(sc, cl) -> (sc+cl, cl) 

3. 화면에 있는 이모티코 중 하나를 삭제
(sc, cl) -> (sc-1. cl)

---

문제 풀이는 다음과 같다.

1. pair<int,int>형 큐를 만든다.

2. 최초의 위치는 1이며, 움직임 횟수는 0이다. 때문에 큐에 {1,0}을 삽입한다.

3. 위의 3가지 케이스를 고려하여 각 케이스에 따른 결과를 큐에 삽입한다. 

        for(int i=0; i<3; i++){
            if(i==1){
                if(sc>1000) break;
                if(arr[sc][sc]==0){
                    arr[sc][sc] = arr[sc][cl]+1;
                    q.push({sc,sc});
                }
            }
            else if(i==2){
                if(sc+cl>1001) break;
                if(arr[sc+cl][cl]==0){
                    arr[sc+cl][cl] = arr[sc][cl]+1;
                    q.push({sc+cl,cl});
                }
            }
            else{
                if(sc<=0) break;
                if(arr[sc-1][cl]==0){
                    arr[sc-1][cl] = arr[sc][cl]+1;
                    q.push({sc-1,cl});
                }
            }
        }

이때 각 케이스에서 값을 벗어나는 상황에 대해 예외처리를 해주는 것을 잊지말자.

4. 큐의 fron의 first = sc = screen값이 목표값일 경우, 누적 시간을 출력하고 종료한다.

 

#include <iostream>
#include <queue>
#define MAX 1002
using namespace std;

int s, arr[MAX][MAX], sc, cl; // screen, clip board

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> s;
    queue<pair<int,int>> q;
    q.push({1,0});
    while(!q.empty()){
        sc = q.front().first;
        cl = q.front().second;
        if(sc==s){
            cout << arr[sc][cl] << "\n";
            exit(0);
        }
        q.pop();
        for(int i=0; i<3; i++){
            if(i==1){
                if(sc>1000) break;
                if(arr[sc][sc]==0){
                    arr[sc][sc] = arr[sc][cl]+1;
                    q.push({sc,sc});
                }
            }
            else if(i==2){
                if(sc+cl>1001) break;
                if(arr[sc+cl][cl]==0){
                    arr[sc+cl][cl] = arr[sc][cl]+1;
                    q.push({sc+cl,cl});
                }
            }
            else{
                if(sc<=0) break;
                if(arr[sc-1][cl]==0){
                    arr[sc-1][cl] = arr[sc][cl]+1;
                    q.push({sc-1,cl});
                }
            }
        }
    }
    return 0;
}