[백준 14226] 이모티콘

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

14226번: 이모티콘

#include <cstdio>
#include <algorithm>
#include <queue>
int S;
struct _st
{
	int cb;		// 클립보드의 이모티콘 수
	int n;		// 화면의 이모티콘 수
	int t;		// 걸린시간
};

std::queue<_st> Q;

// 클립보드의 이모티콘 수를 만드는데 걸린 시간, 화면의 이모티콘 수를 만드는데 걸린 시간
int chk[1000 + 10][1000 + 10];

void init(void)
{
	for (int i = 0; i < S + 2; i++) {
		for (int j = 0; j < S + 2; j++) {
			chk[i][j] = 0x7fffffff;
		}
	}
}


void BFS(void)
{
	// 초기상태
	Q.push({ 0, 1, 0 });	// 클립보드에 있는 이모티콘 수, 화면에 있는 이모티콘 수, 지난시간
	chk[0][1] = 0;			// 클립보드에 이모티콘 0개, 화면에 이모티콘을 1개 만드는데 0초 걸림

	while (!Q.empty()) {
		_st data = Q.front();
		//printf("[before] cb : %d n : %d t : %d\n", Q.front());
		Q.pop();

		// 1. 화면에 있는 이모티콘을 모두 복사하여 클립보드에 저장
		int cv_cb = data.n;
		int cv_t = chk[data.cb][data.n] + 1;
		if (chk[cv_cb][data.n] > cv_t) {
			chk[cv_cb][data.n] = cv_t;
			Q.push({ cv_cb, data.n, cv_t });
			//printf("[ctrlc] cb : %d n : %d t : %d\n", Q.back());
		}
		

		// 2. 클립보드에 있는 모든 이모티콘 화면에 붙여넣기
		if (data.cb != 0) {
			int save_n = data.n + data.cb;
			if (save_n <= S) {	// 화면의 이모티콘 수가 S와 같거나 작을때만 붙여넣기를 수행한다. 
				int save_t = chk[data.cb][data.n] + 1;
				if (chk[data.cb][save_n] > save_t) {
					chk[data.cb][save_n] = save_t;
					Q.push({ data.cb, save_n, save_t });
					//printf("[save] cb : %d n : %d t : %d\n", Q.back());
				}
			}
		}

		// 3. 화면에 있는 이모티콘 중 하나 삭제
		int del_n = data.n - 1;
		int del_t = chk[data.cb][data.n] + 1;
		if (chk[data.cb][del_n] > del_t) {
			chk[data.cb][del_n] = del_t;
			Q.push({ data.cb, del_n, del_t });
			//printf("[del] cb : %d n : %d t : %d\n", Q.back());
		}
	}
}

void output(void)
{
	int ans = 0x7fffffff;
	for (int i = 0; i <= S; i++) {
		if (ans > chk[i][S]) ans = chk[i][S];
	}
	printf("%d", ans);
}


int main()
{
	scanf("%d", &S);
	init();
	BFS();
	output();
	return 0;
}

엄.. 미리 밝히자면 내 코드는 직관적인 대신 효율이 떨어지고 더럽다 ㅋㅋㅋㅋ 그냥 문제가 시키는대로만 짰기 때문.. ㅎ

방향벡터 만들어서 상하좌우 살피는 것 처럼 1, 2, 3 번 동작을 operation 배열에 넣고 i = 0에서 i = 3까지 루프 돌면서 하나씩 수행하도록 코드를 짜는 것이 훨씬 짧고 성능이 좋다. (<- 이렇게 푼 방법은 다시 풀고 추가하겠다. 언젠가...)

 

 

// BFS( ) 함수

S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구해야 하기 때문에 BFS를 사용한다. 

1, 2, 3 번 수행에 우선순위는 없다. 한 번 루프를 돌면서 셋 다 수행할 수 있기 때문에 어떤 동작 수행 후 continue를 해주면 답이 이상하게 나온다. (혹은 안나옴 ^^ 내가 해봄 ^^) 

그래서 각각의 경우를 독립적으로 생각하고 구현해주었다. 

 

[1] 화면에 있는 이모티콘을 모두 복사하여 클립보드에 저장한다. 

int cv_cb = data.n;
int cv_t = chk[data.cb][data.n] + 1;
if (chk[cv_cb][data.n] > cv_t) {
    chk[cv_cb][data.n] = cv_t;
    Q.push({ cv_cb, data.n, cv_t });
    //printf("[ctrlc] cb : %d n : %d t : %d\n", Q.back());
}

이때 걸린 시간은 chk배열에서 '클립보드에 갱신된 이모티콘 수(cv_cb)', '화면에 있는 이모티콘 수(data.n)'를 만드는데 걸린 시간보다 적게 들면 갱신한다. 

 

 

[2] 클립보드에 있는 모든 이모티콘을 화면에 붙여넣는다.

if (data.cb != 0) {
    int save_n = data.n + data.cb;
    if (save_n <= S) {	// 화면의 이모티콘 수가 S와 같거나 작을때만 붙여넣기를 수행한다. 
        int save_t = chk[data.cb][data.n] + 1;
        if (chk[data.cb][save_n] > save_t) {
            chk[data.cb][save_n] = save_t;
            Q.push({ data.cb, save_n, save_t });
            //printf("[save] cb : %d n : %d t : %d\n", Q.back());
        }
    }
}

이 동작 때문에 계속 런타임에러(Out of Bounds)가 났었는데, 그 이유는 save_n이 S를 넘어가도 클립보드에 있는 이모티콘을 화면에 붙여넣도록 코드를 짰었기 때문이다. 이렇게 하면 내가 할당된 chk배열의 크기를 초과할 수 있다. 

따라서 화면의 이모티콘 수가 S와 같거나 작을때(save_n <= S)만 붙여넣기를 수행하도록 했다. 

이때 걸린 시간은 chk배열에서 '클립보드에 있는 이모티콘 수(data.cb)', '화면에 갱신된 이모티콘 수(save_n)'를 만드는데 걸린 시간보다 적게 들면 갱신한다. 

 

 

[3] 화면에 있는 이모티콘 중 하나를 삭제한다. 

int del_n = data.n - 1;
int del_t = chk[data.cb][data.n] + 1;
if (chk[data.cb][del_n] > del_t) {
    chk[data.cb][del_n] = del_t;
    Q.push({ data.cb, del_n, del_t });
    //printf("[del] cb : %d n : %d t : %d\n", Q.back());
}

이때 걸린 시간은 chk배열에서 '클립보드에 있는 이모티콘 수(data.cb)', '화면에 갱신된 이모티콘 수(del_n)'를 만드는데 걸린 시간보다 적게 들면 갱신한다.