[BOJ/백준] 14226 이모티콘

● [문제번호 14226] 이모티콘

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

14226번: 이모티콘

 

● 알아야 할 것

: pair 자료구조와 메소드

: BFS

 

 

● 풀이 과정

: BFS로 구현하려해도 논리적으로 정리되지 않아서

계속 수정을 거듭해도 새어나가는 부분이 있었다.

그래서 결국 구글링을 했는데

BFS로 푼 사람도 있고, DP로 푼 사람도 있고,

무엇보다 풀이도 쉽게 이해되지 않았다.

 

: 클립보드를 전역변수 1개로 처리하려했으나

Queue를 이용하여 화면에 있는 이모티콘의 수가 왔다갔다 하니까

1개의 클립보드로는 구현하기 어렵다는 걸 뒤늦게 깨달았다.

 

그래서 2차원 배열을 이용하여

(view : 화면 이모티콘 수 / clipboard : 클립보드 이모티콘 수)

visited[view][clipboard] = view, clipboard를 만드는 데 걸리는 시간

으로 정의했다.

 

복사 : [view][view]

붙여넣기 : [view + clipboard][clipboard]

삭제 : [view - 1][clipboard]

 

범위를 벗어나거나 방문한적 있는 [view][clipboard] 인 경우

넘기면 된다.

 

● 주의 할 것

: 클립보드를 하나의 전역변수로 놓고

공통으로 사용하려했는데,

Queue를 이용하여 화면에 있는 이모티콘의 수가 왔다갔다 하니

클립보드도 배열로 저장할 필요가 있었다.

이것을 생각해내지 못해 제대로 된 결과를 얻기 어려웠다.

 

: 범위를 벗어난 경우를 처리할 때

S초과를 하면

S초과인 수부터 삭제하며 내려온 방법이 최소 시간일 수 있는 데

이를 간과하게 된다.

 

 

● 참고 할 것

: 풀이과정

https://rebas.kr/749

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// visited : [화면에 있는 이모티콘 수][클립보드에 있는 이모티콘 수]
// 값 = 해당 index의 이모티콘을 화면에 만드는데 걸리는 시간
// 1001이 아니고 2001인 이유 : S보다 큰 수에서 내려오는 경우가 최소 시간일 수 있기 때문에
int visited[2001][2001];
int S;

void bfs()
{
    // {화면 이모티콘 수} 와 {클립보드 이모티콘 수}
    queue<pair<int, int>> q;
    
    // 처음 상태
    // {화면에 이모티콘 1개} , {클립보드 이모티콘 0개}
    q.push(pair<int, int>(1, 0));
    
    while(!q.empty())
    {
        int view = q.front().first;
        int clipboard = q.front().second;
        
        q.pop();
        
        // 완료
        if(view == S)
        {
            cout << visited[view][clipboard];
            return ;
        }
        
        // 복사 / 붙여넣기 / 삭제
        int nextV[3] = {view, view + clipboard, view - 1};
        int nextC[3] = {view, clipboard, clipboard};
        
        for(int i = 0; i < 3; i++)
        {
            // 범위를 벗어난 경우
            // S로 하면 S보다 큰 수에서 내려오는 경우도 있으므로 2*S로 설정
            if(nextV[i] < 0 || 2 * S < nextV[i])
                continue;
                
            // 방문한 적 있는 경우
            // {화면 이모티콘 수} 와 {클립보드 이모티콘 수} 까지 동일해야함
            if(visited[nextV[i]][nextC[i]])
                continue;
            
            visited[nextV[i]][nextC[i]] = visited[view][clipboard] + 1;
            q.push({nextV[i], nextC[i]});
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> S;
    
    bfs();
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [610 - BFS] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1697	숨바꼭질	https://pirateturtle.tistory.com/283
2	13913	숨바꼭질 4	https://pirateturtle.tistory.com/284
3	14226	이모티콘	https://pirateturtle.tistory.com/285
4	13549	숨바꼭질 3	https://pirateturtle.tistory.com/286
5	1261	알고스팟	https://pirateturtle.tistory.com/287