[백준] 14226 이모티콘

백준 14226 이모티콘

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

• 다른 동적 계획법 문제들과 같이 재귀적으로 접근을 시도하였으나, 너비 우선 탐색 (BFS) 활용해야하는 문제였다

• 모든 연산이 1초가 걸리기 때문에 가중치가 모두 같은 경우의 최단거리를 구하는 문제이다

#include<iostream>
#include <utility>
#include<queue>

const int MAX = 2000;
using namespace std;

int S;

//Visit[screen][clipBoard]
bool Visit[MAX][MAX];

int BFS(){
	//queue of pair<pair<screen, clipBoard>, time>
	queue<pair<pair<int, int>, int> > Q;

	Q.push(make_pair(make_pair(1, 0), 0));
	Visit[1][0] = true;    

	while (Q.empty() == 0)
	{
		int screen = Q.front().first.first;
		int clipBoard = Q.front().first.second;
		int time = Q.front().second;
		Q.pop();

		//base case
		if (screen == S) return time;

		//copy
		if (screen > 0 && screen < MAX) {
			if (Visit[screen][screen] == false) {
				Visit[screen][screen] = true;
				Q.push(make_pair(make_pair(screen, screen), time + 1));
			}
		}
		//paste
		if (clipBoard > 0 && screen + clipBoard < MAX){
			if (Visit[screen + clipBoard][clipBoard] == false){
				Visit[screen + clipBoard][clipBoard] = true;
				Q.push(make_pair(make_pair(screen + clipBoard, clipBoard), time + 1));
			}
		}
		//sub
		if (screen > 0 && screen < MAX) {
			if (Visit[screen - 1][clipBoard] == false){
				Visit[screen - 1][clipBoard] = true;
				Q.push(make_pair(make_pair(screen - 1, clipBoard), time + 1));
			}
		}
	}
}


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

	cin >> S;

	int R = BFS();
	cout << R;

	return 0;
}

📌참고자료

• 백준 14226 이모티콘 풀이(BFS)
  https://yabmoons.tistory.com/74