백준 14226 이모티콘 - 큐를 이용한 너비 우선 탐색

문제출처
https://www.acmicpc.net/problem/14226

소스코드

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

bool visit[2000][2000]; // [화면][클립보드]

int bfs(int s){
    queue<pair<pair<int, int>, int> > q;  // 화면, 클립보드, 시간
    int screen, clipboard, time;
    q.push(make_pair(make_pair(1,0), 0));
    visit[1][0] = true;
    // 큐를 이용한 너비 우선 탐색
    while(!q.empty()){
        screen = q.front().first.first;
        clipboard = q.front().first.second;
        time = q.front().second;
        q.pop();

        // 결과 출력
        if(screen == s)
            break;

        // 너비우선탐색
        // 화면 이모티콘 클립보드로, 화면에서 하나 지우기
        if(screen > 0 && screen < 2000){
            if(visit[screen][screen] == false){
                visit[screen][screen] = true;
                q.push(make_pair(make_pair(screen,screen), time+1));
            }
            if(visit[screen-1][clipboard] == false){
                visit[screen-1][clipboard] = true;
                q.push(make_pair(make_pair(screen-1,clipboard), time+1));
            }
        }
        // 클립보드에 있는거 붙여넣기
        if(clipboard > 0 && screen + clipboard < 2000){
            if(visit[screen + clipboard][clipboard] == false){
                visit[screen + clipboard][clipboard] = true;
                q.push(make_pair(make_pair(screen + clipboard,clipboard), time+1));
            }
        }
    }
    return time;
}

int main(){
    int input;
    cin >> input;
    cout << bfs(input) << '\n';
}

큐를 이용한 너비우선탐색

백준에 있는 숨바꼭질 시리즈와 비슷한 느낌으로 풀이를 했다.

불 배열 visit는 2차원 배열로 [화면][클립보드]를 저장하고 있어 보다 풀이가 쉬워진다.
bfs를 할 때 큐 안에 처음 상태를 입력해준 뒤 큐의 앞 원소를 pop 해서 그 원소를 통해 조건에 따라 탐색을 시작했다.

• 조건의 종류
  • 공통 조건 : visit배열에서 아직 탐색하지 않은 곳일 것
  • 화면 이모티콘을 클립보드로 : 화면에 내용이 있을 것, 최대값의 이하 범위 (넘는 경우가 없음)
  • 클립보드에 있는거 붙여넣기 : 클립보드에 이모티콘이 있을 것, 둘 합쳐 최대값 이하
  • 화면에서 하나 지우기 : 화면에 내용이 있어야 함

이런 조건들을 거쳐 트리 만들듯 큐를 이용해서 너비우선 탐색을 하면 된다.

개인생각

처음 탐색 문제들을 풀 때는 잘 사용하지 못했던 큐지만 pair을 안 이후로 더 자유롭게 사용할 수 있는 것 같다. 메모리를 많이 사용하지만 확실히 이해하기 쉬운 코드들이 많아지고 있다