백준 14226 (이모티콘)

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

14226번: 이모티콘

해당 문제는 영선이가 효빈에에게 이모티콘 S개를 보내려 할 때 조건에 따라 이모티콘의 수를 변경하며 최소 몇 초 만에 S개의 이모티콘을 보낼 수 있는지 구하는 문제이다.

이모티콘의 수를 변경할 수 있는 방법은 다음과 같으며 각 방법을 시행시 1초가 소요된다.

조건 

1. 화면에 있는 이모티콘 전부를 클립보드에 복붙 하는경우 (따라서 화면에 이모티콘이 0이라면 수행 X)

2. 화면에 있는 이모티콘 중 하나를 없애는 경우 (따라서 화면에 이모티콘이 0이라면 수행 X)

3. 클립보드에 있는 이모티콘을 화면에 추가하는 경우 (따라서 클립보드에 이모티콘이 없다면 수행 X)

위와 같은 조건에 맞게 이모티콘의 수를 조절할 수 있다.

 

풀이 :

해당 문제는 BFS를 이용한 각 조건에 맞는 경우의 수를 모두 탐색하며 최솟값을 구하면 된다. 이때 주의해야 할 점은 다음과 같다.

1. 만약 화면에 있는 이모티콘 1개와 클립보드에 있는 이모티콘이 0개일 때 해당 경우의 조건을 수행 시 visit 배열에 체크해주어야 한다. EX -> visit [화면 이모티콘 개수][클립 보드 이모티콘 개수] == 0 일 때 즉 해당 경우를 방문한 적 없을 때 에만 수행

2. 문제의 조건중 보내려는 최대 이모티콘의 개수는 1000개로 설정이 되어있다 따라서 클립보드에서 화면으로 복붙하는 경우 1000을 넘게 된다면 visit 배열에 체크 시 런타임 애러가 일어난다 따라서 항상 클립보드에서 화면으로 복사 및 붙여 넣기 수행 시 화면 이모티콘 + 클립보드 이모티콘 개수가 1000과 같거나 작은지 확인하여야 한다.

#include <algorithm>
#include <iostream>
#include <string>
#include <queue>

using namespace std;

int visit[1001][1001];
int targetNUm;
struct Node{
	int mCnt, bCnt;
	int cnt;
};

int bfs(int sm, int sb){
	queue<Node> qu;
	qu.push({ sm, sb });
	visit[sm][sb] = 1;

	while (!qu.empty()){
		Node now = qu.front();
		if (now.cnt > 1000) return 0;
		if (now.mCnt == targetNUm) return now.cnt;
		if (now.mCnt > 0){
			// 화면에서 클립보드로 복붙
			if (visit[now.mCnt][now.mCnt] == 0){
				visit[now.mCnt][now.mCnt] = 1;
				qu.push({ now.mCnt, now.mCnt, now.cnt + 1 });
			}
			// 화면의 이모티콘 1개 제거
			if (visit[now.mCnt - 1][now.bCnt] == 0){
				visit[now.mCnt - 1][now.bCnt] = 1;
				qu.push({ now.mCnt - 1, now.bCnt, now.cnt + 1 });
			}
		}
		if (now.bCnt > 0){
			// 클립보드의 이모티콘 화면으로 복붙
			if (now.mCnt + now.bCnt <= 1000 && visit[now.mCnt + now.bCnt][now.bCnt] == 0){
				visit[now.mCnt + now.bCnt][now.bCnt] = 1;
				qu.push({ now.mCnt + now.bCnt, now.bCnt, now.cnt + 1 });
			}
		}
		qu.pop();
	}

}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> targetNUm;
	cout << bfs(1, 0) << endl;

}