💡 너비 우선 탐색/다이나믹 프로그래밍/그래프 이론/그래프 탐색
Memory 16852KB Time 8ms Code Length 1019B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
struct INFO
{
int monitor;
int clipboard;
int t;
};
queue<INFO> q;
int S; // 목표
int visited[2000][2000] = { 0 }; // 모니터 이모티콘 갯수 방문일지
int result;
void bfs() {
while (!q.empty()) {
int m = q.front().monitor;
int c = q.front().clipboard;
int t = q.front().t; q.pop();
if (m == S) {
result = t;
return;
}
// 1. 클립보드 저장(덮어쓰기)
int nc = m;
if (visited[m][nc] == 0) {
visited[m][nc] = 1;
q.push({ m,nc,t + 1 });
}
// 2. 클립보드를 화면에 붙여넣기
if (m + c <= 1500 && c!=0) {
if (visited[m + c][c] == 0) {
visited[m + c][c] = 1;
q.push({ m + c, c, t + 1 });
}
}
// 3. 이모티콘 하나 삭제
if (m > 0) {
if (visited[m - 1][c] == 0) {
visited[m - 1][c] = 1;
q.push({ m - 1, c, t + 1 });
}
}
}
}
int main() {
scanf("%d", &S);
q.push({ 1,0, 0 });
visited[1][0] = 1;
bfs();
printf("%d\n", result);
}
이 코드는 BFS(너비 우선 탐색) 알고리즘을 사용하여 이모티콘 작업을 수행하는 프로그램이다.
시작할 때, 화면에 1개의 이모티콘만 존재하고 클립보드는 비어있다.
큐에 이모티콘 상태와 작업 시간을 저장하고, 방문 여부를 체크한다.
큐가 빌 때까지 다음 작업을 반복한다.
현재 이모티콘 상태가 목표와 같으면 작업 시간을 결과로 저장하고 종료한다.
클립보드에 복사, 클립보드 내용을 화면에 붙여넣기, 이모티콘 하나 삭제 세 가지 작업을 수행한다.
각 작업을 수행한 후, 새로운 상태를 큐에 저장하고 작업 시간을 증가시킨다.
BFS 알고리즘을 통해 모든 가능한 상태를 탐색하고, 최종적으로 목표 상태에 도달하는데 걸리는 최소 작업 시간을 출력한다.
