끄적끄적 코딩
article thumbnail

이모티콘을 가장 빠르게 원하는 개수만큼 만드는 문제입니다.
BFS로 문제를 해결했습니다.

--1초간 할 수 있는 행동 (1가지만 가능)--
1. 화면의 이모티콘 복사
2. 복사된 이모티콘 붙여넣기
3. 이모티콘 한글자 제거

위의 세가지 경우에 대해서 전부 큐에 넣어주어서
모든 경우를 너비탐색 방식으로 확인하면서 찾는 경우 출력해주었습니다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX_VALUE 1001
using namespace std;

struct component {
	int display, clipboard, time;	
};

int main(int argc, char *argv[])
{
	int s;
	int d, c, t;
	int result = 0;
	bool visit[MAX_VALUE][MAX_VALUE];
	queue<component> q;
	
	cin >> s;
	
	q.push({1, 0, 0});
	visit[1][0] = true;
	
	while(!q.empty()) {
		d = q.front().display;
		c = q.front().clipboard;
		t = q.front().time;
		q.pop();
		
		if(d == s) {
			result = t;
			break;
		}
		
		if(d < MAX_VALUE) {
			if(!visit[d][d]) {
				visit[d][d] = true;
				q.push({d, d, t+1});
			} 
			if(c > 0 && d + c < MAX_VALUE) {
				if(!visit[d+c][c]) {
					visit[d+c][c] = true;
					q.push({d+c, c, t+1});
				}
			}
			if(!visit[d-1][c]){
				visit[d-1][c] = true;
				q.push({d-1, c, t+1});	
			}
		}
	}
	
	cout << result << endl;
	
	return 0;
}

검색 태그