백준 14226 이모티콘 - 2차원 배열로 상태저장 bfs - c++

링크

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

14226번: 이모티콘

아이디어

오랜만에 bfs관련 풀어본 문제.

이문제는 주의해야 할점이, 클립보드에 복사한 이모티콘 갯수는 몇번이고 재사용이 가능하다는 것이다.

처음에는 문제에서 요구한 조건을 잘못 이해해서, 결국 '어 복사 붙여넣기 하는 시간은 2초 걸리네?'라고 잘 못 이해했다.

1>>2>>4>>6 이런식으로 복사한 걸 계속 쓸 수도 있는 것이다.

 

결국 이 문제를 풀기 위해선 '현재 클립보드에 있는 이모티콘의 갯수' 까지도 상태를 저장해 가면서 풀 수 밖에 없는 구조다.

 

그렇기 위해서는 필연적으로, visited bool 배열역시, 현재 이모티콘 갯수와 현재 클립보드 이모티콘 갯수 2개를 저장할 수 있어야 하므로 2차원으로 설정을 해놔야 한다.

그렇다면 queue에는? time을 pair로 만들지 않고 할 수도 있지만 pair을 만들어서 사용한다면 다음과 같은 이중 pair꼴로 queue를 셋팅해야한다.

 

코드

#include <iostream>
#include <queue>
using namespace std;
int s;
const int MAX=2000;
bool visited[MAX][MAX];
 
int bfs(){
    queue<pair<pair<int,int>,int>> Q;
    Q.push(make_pair(make_pair(1,0),0));
    visited[1][0] = true;
 
    while(!Q.empty()){
        int num = Q.front().first.first;
        int clip_num = Q.front().first.second;
        int time = Q.front().second;
        Q.pop();
 
        if(num==s) return time;
        if(num<MAX){
            if(!visited[num][num]){
                visited[num][num]=true;
                Q.push(make_pair(make_pair(num,num),time+1));
            }
        }
        if(num>0){
            if(!visited[num-1][clip_num]){
                visited[num-1][clip_num]=true;
                Q.push(make_pair(make_pair(num-1,clip_num),time+1));
            }
        }
        if(num+clip_num<MAX){
            if(!visited[num+clip_num][clip_num]){
                visited[num+clip_num][clip_num]=true;
                Q.push(make_pair(make_pair(num+clip_num,clip_num),time+1));
            }
        }
    }
}
 
int main(void){
    cin>>s;
    int result = bfs();
    cout<<result;
}