이모티콘을 가장 빠르게 원하는 개수만큼 만드는 문제입니다.
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;
}
'알고리즘' 카테고리의 다른 글
[C++] 백준 2252번 줄 세우기 (0) | 2021.08.25 |
---|---|
[C++] 백준 2533번 사회망 서비스(SNS) (0) | 2021.08.25 |
[C++] 백준 1926번 그림 (0) | 2021.08.18 |
[C++] 백준 1715번 카드 정렬하기 (0) | 2021.08.09 |
[C++] 백준 1339번 단어 수학 (0) | 2021.08.09 |