[14226] 이모티콘

풀이

클립보드에 있는 이모티콘의 수를 s, 클립보드에 있는 이모티콘의 수를 c라고할 때 현재상태 (s,c)에서 다음으로 진행할 수 있는 경우는 세 가지뿐입니다.

1. (s,c) -> (s,s) : 클립보드에 붙혀넣기
2. (s,c) -> (s+c,c) :스크린에 붙혀넣기
3. (s,c) -> (s-1,c) : 1개 지우기

이 문제의 핵심은 이 문제가 BFS 문제인 것을 알고 이를 구조화하는데 달려있다고 생각합니다. 위와 같이 s와 c를 정의하면 1000*1000 배열을 모두 한 번씩만 탐색하므로 1초 안에 해결할 수 있는 문제가 됩니다. 이전까지 풀었던 기본 BFS 문제는 인접행렬에서 4방향으로 인접한 칸으로만 이동하는 것으로 접근을 했었는데 이 문제는 s와 c의 개념을 만들어서 멀리 떨어져있지만 [0:1000][0:1000]의 범위에 있는 다른 칸과도 인접하다는 개념을 적용해서 풀 수 있습니다.

코드

#include <cstdio>
#include <queue>
using namespace std;
#define MAX 1000
bool check[MAX + 1][MAX + 1];
int time[MAX + 1][MAX + 1];

int dfs(int dst) {
	queue<pair<int,int> > q;
	check[1][0] = true;
	q.push(make_pair(1,0));
	pair<int, int> curr, next;
	while (!q.empty()) {
		curr = q.front(); q.pop();
		if (curr.first == dst) return time[curr.first][curr.second];
		//1. (s,c) -> (s,s)
		next = curr;
		next.second = next.first;
		if (check[next.first][next.second] == false) {
			check[next.first][next.second] = true;
			q.push(next);
			time[next.first][next.second] = time[curr.first][curr.second] + 1;
		}
		//2. (s,c) -> (s+c,c)
		next = curr;
		next.first += next.second;
		if (next.first <= 1000 && check[next.first][next.second] == false) {
			check[next.first][next.second] = true;
			q.push(next);
			time[next.first][next.second] = time[curr.first][curr.second] + 1;
		}
		//3. (s,c) -> (s-1,c)
		next = curr;
		next.first -= 1;
		if (0 <= next.first && check[next.first][next.second] == false) {
			check[next.first][next.second] = true;
			q.push(next);
			time[next.first][next.second] = time[curr.first][curr.second] + 1;
		}
	}

}

int main(void) {
	int s = 0;
	scanf("%d", &s);
	printf("%d\n", dfs(s));

	return 0;
}