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

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int s, ans = 1e9;
    cin >> s;
    
    queue<tuple<int, int, int> > q;
    q.push(make_tuple(1, 1, 1));
    bool v[1001] = {}; //방문확인
    
    while(!q.empty()) { //bfs
        int now = get<0>(q.front());
        int copy = get<1>(q.front());
        int value = get<2>(q.front());
        q.pop();
        
        if(now == s) { //원하는 개수로 맞추었다면 탐색 종료
            ans = value;
            break;
        }
        
        value++; //수행시간 1 증가
        
        if(now <= 1000 && !v[now]) { //다음단계로 단, 1000을 넘어가면 무조건 -1 만 반복하므로, 사전에 차단
            q.push(make_tuple(now+copy, copy, value)); //복사한 것을 붙여놓기
            if(now != copy) q.push(make_tuple(now, now, value)); //클립보드로 복사하기
            if(now > 2) q.push(make_tuple(now-1, copy, value)); //화면에서 1개 제거하기
            v[copy] = true; //방문확인
        }
    } cout << ans;
}

 

풀이 : BFS

 

현재 화면에 있는 개수, 클립보드에 복사한 개수, 수행시간 을 하나로 묶은 것을 큐로 다뤄서 BFS을 합니다.

 

3가지 방식으로 탐색을 진행합니다.

 

초기 값은 클립보드에 1개를 복사한 것으로 시작합니다.

 

1. 복사한 것을 붙여놓기

2. 클립보드로 복사하기 (단 클립보드에 있는 것과 복사할 것이 같지 않다면 시행하지 않습니다)

3. 화면에서 1개 제거하기 (단 2개 이하이면 하는 의미가 없으므로 시행하지 않습니다)

 

탐색과정에서 원하는 개수만큼이 되면 바로 종료합니다 (완전탐색을 하지 않습니다!)

 

중복을 줄이기 위해서 방문 확인을 해주어야 합니다.

 

화면개수와, 클립보드에 있는 개수로 이차원배열을 만든 다음 방문확인을 해줄수 있으나,

 

일차원 배열만으로도 가능합니다.

 

if(now <= 1000 && !v[now]) {
            q.push(make_tuple(now+copy, copy, value)); //복사한 것을 붙여놓기
            if(now != copy) q.push(make_tuple(now, now, value)); //클립보드로 복사하기
            if(now > 2) q.push(make_tuple(now-1, copy, value)); //화면에서 1개 제거하기
            v[copy] = true; //방문확인
        }

 

위의 코드를 보면 처음에는 v[now]  ( 화면에 있는 이모티콘 개수인 상태로 이미 탐색을 했었다면 ) 으로 확인

그 다음은 v[copy] = true (클립보드에 있는 개수를 가지고 방문확인을 했다고 해줍니다) 을 합니다.

 

v[now] v[now] = true 또는 v[copy] v[copy] = true 이런 식으로는 불가합니다.

반드시 처음에는 v[now] 그 다음엔 v[copy] = true 을 해주어야 합니다.

 

이유

 

S > 10 인 경우

 

1 1 1  (v[1] = true)

2 1 1  (v[1] = true)

            3 1 1   (v[1] = true)                                                                2 2 1      (v[2] = true)

4 1 1(실행됨)    3 3 1 (실행됨)   2 1 1(실행 안됨)                              4 2 1 (실행)   

.

 

여기서 알수 있는 것은 2 1 1이 중복되는 것을 방문확인을 통해서 방지했습니다.

 

이렇게 구현 하게된 이유는

서순이 화면에 있는 개수 -> 클립보드에 있는 개수 입니다.

 

즉 클립보드에 n개가 있기위해선 이전에 화면에 있는 개수가 n개이어야만 합니다.

즉 클립보드에 n개가 복사된 순간, 이제 더이상 화면에 n개가 있는 경우는 볼 필요가 없어집니다.

 

그래서

while (v[now] == false) {

///생략

v[copy] = true

}

로 방문탐색을 했습니다.

 

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

14226번: 이모티콘