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

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

숨바꼭질2 문제와 거의 똑같은 문제다. 경로가 겹칠 수 있으므로 방문 처리는 pop과 동시에 해준다. 큐에 들어가는 원소는 총 아래의 세가 정보를 담고 있어야 한다. 

1. 모니터 속 이모티콘 개수 (monitor)
2. 클립보드 이모티콘 개수 (board)
3. 시간 (time)

 

나는 obj라는 구조체를 선언해 세 가지 정보를 담았다.

 

typedef struct{
    int monitor;
    int board;
    int time;
}obj;

 

큐에 push 되는 경우의 수는 아래와 같다. 

 

1. 클립보드에 복사 (board = monitor)
2. 클립보드에서 화면으로 복붙 (monitor += board) - map 초기화
3. 화면에서 하나 삭제 (monitor -= 1)  - map 초기화

 

이를 그대로 코드로 구현하면 된다. bfs의 종료 조건은 'monitor == 입력값'이다. 이 조건을 만족하면 obj의 time 변수를 출력해주면 된다. 

 

#include <iostream>
#include <queue>
using namespace std;

typedef struct{
    int monitor;
    int board;
    int time;
}obj;

int map[1001];

int main(){
    
    int dest;
    cin >> dest;
    
    queue<obj> q;
    q.push({1, 0, 0});
    
    obj tmp;
    
    while(!q.empty()){
        tmp = q.front();
        q.pop();
        
        map[tmp.monitor] = 1;
        
        if(tmp.monitor == dest){
            cout << tmp.time << endl;
            break;
        }
        
        // 화면에서 하나 삭제
        if(tmp.monitor - 1 >= 1 && !map[tmp.monitor - 1])
            q.push({tmp.monitor - 1, tmp.board, tmp.time + 1});
        
        // 클립보드에서 화면으로 복붙
        if(tmp.monitor + tmp.board <= 1000 && !map[tmp.monitor + tmp.board])
            q.push({tmp.monitor + tmp.board, tmp.board, tmp.time + 1});
            
        // 클립보드에 복사
        q.push({tmp.monitor, tmp.monitor, tmp.time + 1});
        
        
    }
    
    
    return 0;
}