[백준/c++] BOJ 14226 - 이모티콘

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

14226번: 이모티콘

 

문제 설명

1개의 스마일 이모티콘을 가지고 3가지 연산만 사용하여 S개를 만드려고 한다.

1. 화면의 이모티콘을 복사하여 클립보드에 저장 (클립보드 <= 화면)

2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 (화면 <= 클립보드)

3. 화면에 있는 이모티콘 중 하나 삭제 (화면 - 1)

모든 연산은 1초가 걸리며 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구한다.

S (2 <= S <= 1000)

 

해결

visited 배열 [화면][클립보드] 의 2차원으로 방문 처리를 해 주었다.

 

각 연산을 하기 위한 조건을 만족하면,  모든 연산을 처리해 주면서 방문 처리를 해 주었다.

 

1 -> 화면에 이모티콘이 1개 이상 있고 visited[화면][화면]에 방문하지 않은 경우

2 -> 클립보드에 이모티콘이 1개 이상 있고 visited[화면 + 클립보드][클립보드]에 방문하지 않은 경우

3 -> 화면에 이모티콘이 1개 이상 있고 visited[화면 - 1][클립보드]에 방문하지 않은 경우

 

모든 연산을 처리하다가 화면의 이모티콘이 S개가 되면 bfs를 중단한다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n;
int visited[2001][2001];

int bfs() {
	queue<tuple<int, int, int>> q;
	q.push({ 1, 0, 0 });
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		int screen = get<0>(cur), clip = get<1>(cur), time = get<2>(cur);

		if (screen == n) return time;

		if (screen && !visited[screen][screen]) {
			q.push({ screen, screen, time + 1 });
			visited[screen][screen] = 1;
		}

		if (clip && screen + clip <= 2000 && !visited[screen + clip][clip]) {
			q.push({ screen + clip, clip, time + 1 });
			visited[screen + clip][clip] = 1;
		}

		if (screen - 1 >= 0 && !visited[screen - 1][clip]) {
			q.push({ screen - 1 , clip, time + 1 });
			visited[screen - 1][clip] = 1;
		}
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	cout << bfs();
}