백준 14226번 이모티콘 C++

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

 

bfs를 이용하여 문제를 해결하였다.

현재 화면, 클립보드 두 개의 정보를 이용하여 2차원 방문 배열을 기록하면서 시간의 최솟값을 구하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

struct Info {
	int screen;
	int clipBoard;
	int cnt;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int s;
	cin >> s;
	vector<vector<bool>> found(2001, vector<bool>(2001, false));
	queue<Info> q;
	q.push({ 1,0,0 });
	found[1][0] = true;
	int ans = 0;
	while (true) {
		auto curr = q.front();
		q.pop();
		if (curr.screen == s) {
			ans = curr.cnt;
			break;
		}
		if (!found[curr.screen][curr.screen]) {
			found[curr.screen][curr.screen] = true;
			q.push({ curr.screen,curr.screen,curr.cnt + 1 });
		}
		if (curr.screen + curr.clipBoard <= 2000 &&
			!found[curr.screen + curr.clipBoard][curr.clipBoard]) {
			found[curr.screen + curr.clipBoard][curr.clipBoard] = true;
			q.push({ curr.screen + curr.clipBoard ,curr.clipBoard,curr.cnt + 1 });
		}
		if (curr.screen - 1 >= 0 && !found[curr.screen - 1][curr.clipBoard]) {
			found[curr.screen - 1][curr.clipBoard] = true;
			q.push({ curr.screen - 1,curr.clipBoard,curr.cnt + 1 });
		}
	}
	cout << ans;
};