[백준] 14226번 이모티콘

www.acmicpc.net/problem/14226

14226번: 이모티콘

처음에는 BFS인지 DP인지 헷갈려서 DP로 접근했다가 틀리고 BFS로 풀었다.

최단시간에 이모티콘을 만들어야 하므로 DFS가 아니라 BFS로 풀어야 한다. 최단경로, 최단시간 이런 것을 구해야하는 문제라면 BFS를 의심해보자.

이 문제에서는 저 visited를 체크하는 것이 관건인 것 같다.

나는 visited를 map에 저장해주었다.

visited[(5, 3)]은 화면에 이모티콘에 5개가 있고 클립보드에 이모티콘이 3개 있는 상태에 도달한 적이 있는지 없는지를 저장한다.

한 번 방문했으면 다시 방문할 필요가 없는 이유가 BFS이기 때문에 그 이후에 방문하면 걸린 시간이 무조건 더 많이 걸리기 때문이다. 최단시간이 걸리는 경우를 구해야 하므로 한 번 방문했으면 다시 방문할 필요가 없다.

큐에 들어가는 원소는

(화면에 있는 이모티콘 개수, 클립보드에 저장된 이모티콘 개수, 지금 상태까지 몇 초가 걸렸는지)

이렇게 생긴 튜플이다.

큐에 넣을 때는 튜플의 3번째 원소는 무조건 1을 증가한다. 연산 하나에 1초가 걸리기 때문이다.

#include <iostream>
#include <queue>
#include <tuple>
#include <map>
using namespace std;

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	queue<tuple<int, int, int>> q; // 화면에 있는 이모티콘 개수, 클립보드에 있는 이모티콘 개수, 몇 초 걸렸는지
	q.push(make_tuple(1, 0, 0));
	map<pair<int, int>, bool> visited;
	while (!q.empty()) {
		tuple<int, int, int> cur = q.front();
		int emoticonNum = get<0>(cur);
		int clipboardNum = get<1>(cur);
		int seconds = get<2>(cur);
		q.pop();
		if (emoticonNum == n) {
			cout << seconds;
			break;
		}
		if (!visited[make_pair(emoticonNum, clipboardNum)]) {
			visited[make_pair(emoticonNum, clipboardNum)] = true;
			if (get<1>(cur) > 0) { // 클립보드가 비어있지 않으면 화면에 붙여넣기
				q.push(make_tuple(emoticonNum + clipboardNum, clipboardNum, seconds + 1));
			}
			if (get<0>(cur) > 1) { // 화면에 있는 이모티콘 개수가 2 이상이면 화면에 있는 이모티콘 하나 삭제
				q.push(make_tuple(emoticonNum - 1, clipboardNum, seconds + 1));
			}
			q.push(make_tuple(emoticonNum, emoticonNum, seconds + 1)); //현재 화면의 상태를 클립보드에 저장
		}
	}
	return 0;
}