알고리즘 :: 백준 :: BFS :: 14226 :: 이모티콘

문제

문제접근

문제 이해

• 우리가 취할 수 있는 액션은 세 가지입니다.
  1. 화면의 이모티콘 개수는 그대로, 클립보드 개수는 화면의 이모티콘 개수로 변경.
  2. 화면의 이모티콘 개수는 기존 + 클립보드 개수로 변경, 클립보드 개수는 그대로.
  3. 화면의 이모티콘 개수는 기존 - 1로 변경, 클립보드 개수는 그대로.
• 모든 연산은 1초가 걸리고 최소시간을 구하는 문제이므로 BFS를 사용해서 풀 수 있습니다.

풀이 1

• 우리가 지금까지 알고있던 방법을 그대로 사용해봅시다.
• 화면의 이모티콘 개수 cnt와 클립보드의 이모티콘 개수 clip이 있습니다.
• queue를 만들고, 위 세 가지 액션을 그대로 적용해봅시다.
  1. q.push({cnt, cnt}) → 복사
  2. q.push({cnt + clip, clip}) → 붙혀넣기
  3. q.push({cnt - 1, clip}) → 하나 제거
• 이때 cnt + clip과 cnt - 1이 최대범위를 넘지 않도록 조건문을 잘 설정해주면 됩니다.
• 이 문제에서는 이전과 달리 따로 방문 여부를 체크하지 않습니다.
  왜냐하면, 처음에 이모티콘 개수가 1일 때, 복사하고 난 뒤 방문표시를 해버리면 1은 이미 방문된 점이므로 조건문에 들어가지 않아 붙혀넣기가 불가능하기 때문입니다.
• 대신 이 문제에서는 복사 여부를 체크합니다.
  왜냐하면, 복사는 cnt의 값이 변하지 않고 방문 여부도 체크하지 않으므로 무한 loop를 일으킬 가능성이 있기 때문입니다.

풀이 2

• <풀이 1>에는 단점이 있습니다.
  • 가장 큰 단점은 너무 많은 검사를 하게된다는 점입니다.
    • 원인은 바로 방문 여부 비체크 때문입니다. 자칫 잘못하면 TLE나 MLE를 유발할 수 있습니다.
    • 방문 여부를 체크하는 이유는 중복검사를 회피하기 위해서입니다.
      하지만, 방문 여부를 체크하지 않으니 중복검사를 피할 길이 없게됩니다.
  • 두 번째 단점은 이 문제가 엄청나게 많은 간선이 존재하는 그래프와 같다는 점입니다.
    • 예를 들어, 이모티콘 10개를 만들기 위해서는 수많은 경우의 수가 있습니다.
      • 1을 복사하고 10번 붙혀넣기 해서 만드는 경우도 있고
      • 1을 복사하고 붙혀넣고 또 복사하고 붙혀넣는 것을 반복해서 만드는 경우도 있습니다.
    • 즉, 이 문제는 N개의 이모티콘(정점)에 대해 $N \times (N - 1) / 2$개 간선이 있는 그래프와 같습니다.
• 따라서 위 두 가지 단점을 모두 극복하기 위해서 이모티콘의 개수 표현 방법을 바꿉니다.
  • 기존 → 개수로 이뤄진 1차원 배열
  • 변경 → 개수, 클립보드 개수로 이뤄진 2차원 배열
• time[][]이라는 행이 화면상의 이모티콘 개수, 열이 클립보드의 이모티콘 개수인 2차원 배열을 만듭니다.
  • 만일 time[cnt] [cnt] == -1이면 아직 방문하지 않은(?) 이모티콘 개수이므로 복사가 가능한 상태입니다.
  • 만일 time[cnt + clip] [clip] == -1이면 붙혀넣기가 가능한 상태입니다.
  • 만일 time[cnt - 1] [clip] == -1이면 하나 지우기가 가능한 상태입니다.

코드

풀이 1

#include <iostream>
#include <queue>
#include <tuple>
#define MAX 1001
using namespace std;
int S, copied[MAX];

int solve() {
	queue<tuple<int, int, int>> q;
	q.push({1, 0, 0});
	while (!q.empty()) {
		int cnt, clip, time; tie(cnt, clip, time) = q.front();
		if (cnt == S) return time;
		q.pop();
		int nTime = time + 1;
		if (cnt > 2) q.push({cnt - 1, clip, nTime});
		if (clip != 0 && cnt + clip < MAX) q.push({cnt + clip, clip, nTime});
		if (!copied[cnt]) q.push({cnt, cnt, nTime}), copied[cnt] = true;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> S;
	cout << solve();
}

풀이 2

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int S, time[1001][1001];

int solve() {
	queue<pair<int, int>> q;
	q.push({1, 0});
	time[1][0] = 0;
	while(!q.empty()) {
		int now = q.front().first, clip = q.front().second;
		q.pop();
		int next1 = now + clip, next2 = now - 1;
		if (time[now][now] == -1) // 복사하는 경우
			time[now][now] = time[now][clip] + 1, q.push({now, now});
		if (next1 <= S && time[next1][clip] == -1) // 붙혀넣기 하는 경우 
			time[next1][clip] = time[now][clip] + 1, q.push({next1, clip});
		if (next2 >= 0 && time[next2][clip] == -1) // 하나 지우는 경우
			time[next2][clip] = time[now][clip] + 1, q.push({next2, clip});
	}
    // S개를 만드는 모든 경우의 수 중 가장 최소 시간 걸린 거 찾기.
	int ans = -1;
	for (int i = 1; i <= S; ++i)
		if (ans == -1 || ans > time[S][i]) ans = time[S][i];
	return ans;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> S;
	memset(time, -1, sizeof(time));
	cout << solve();
}

결과