[알고리즘] 백준 14226번: 이모티콘 (C++)

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

14226번: 이모티콘

2차원 배열을 활용하여 BFS로 풀 수 있었다.

int emozi[현재 클립보드][현재 화면에 있는 이모티콘 수];

이렇게 두고 '현재 화면에 있는 이모티콘 수'가 s가 되면 시간이 얼마큼 흘렀는지 출력하게끔 BFS를 짜주면 된다.
3가지 모든 연산의 가중치가 1이라 가능했다.

---

[AC 코드]

의문점 (틀왜맞?): 주어진 범위는 1000 이하가 맞으나 MAX가 1000 + 1인데 되는 이유가 무엇일까? 첫 제출에는 2000 + 1로 MAX 잡고 제출하니 맞았었다. 혹시나 하는 마음에 MAX를 1000 + 1로 잡았는데 되는 이유가 무엇일까

#include <iostream>
#include <queue>
#include <utility>
#define MAX 1000 + 1 // 복사 붙여넣기 했을 때, 1000 넘는 경우도 있을 거 같음
using namespace std;

int s;
bool visited[MAX][MAX];
int emozi[MAX][MAX]; // row = clipboard, col = emozi

void bfs() {
	queue<pair<int, int>> q;
	q.push(make_pair(0, 1));
	visited[0][1] = 1;
	while (!q.empty()) {
		int clip = q.front().first;
		int board = q.front().second;

		if (board == s) {
			cout << emozi[clip][board];
			return;
		}

		q.pop();

		// 화면 복사 클립 보드 저장
		int one = board;
		if (one < MAX && !visited[one][board]) {
			visited[one][board] = 1;
			emozi[one][board] = emozi[clip][board] + 1;
			q.push(make_pair(one, board));
		}

		// 클립보드에 있는 이모티콘 화면에 복사
		int two = clip;
		if (board + two < MAX && !visited[clip][board + two]) {
			visited[clip][board + two] = 1;
			emozi[clip][board + two] = emozi[clip][board] + 1;
			q.push(make_pair(clip, board + two));
		}

		// 화면에 이모티콘 하나 삭제
		int three = board - 1;
		if (three > 0 && !visited[clip][three]) {
			visited[clip][three] = 1;
			emozi[clip][three] = emozi[clip][board] + 1;
			q.push(make_pair(clip, three));
		}
	}
}

int main() {
	cin >> s;
	bfs();
	return 0;
}