백준 14226. 이모티콘
알고리즘 기초 문제 중 610 - BFS
1. 간단 설명
이전 숨바꼭질 문제와 굉장히 유사한 문제
좌표를 이동하는 대신에 이모티콘의 개수를 조절한다
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
- 각 연산은 1초
- 복사시 이전에 클립보드에 있던 내용은 덮어쓰기됨
- 클립보드가 비어있다면 붙여넣기는 불가능
- 일부만 클립보드에 복사하는 것도 불가능
- 클립보드에 있는 이모티콘 중 일부를 삭제하는것은 불가능
- 화면에 이모티콘을 붙여넣기하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가됨
1개의 이모티콘이 있을 때, S개의 이모티콘을 만드는데 걸리는 시간의 최소값을 구하는 프로그램 작하기
2. 예시
예제 1) S = 2인 경우 연산1, 연산2 총 2초
예제 2) S = 4인 경우 연산1, 연산2, 연산1, 연산2 총 4초
예제 3) S = 6인 경우 연산1, 연산2 (현재 화면에 2개) 연산1, 연산2, 연산2 (현재 화면에 6개) 총 5초
예제 4) S = 18
1,0,0 {스크린, 클립보드, 초} (복사) 1,1,1 (붙여넣기) 2,1,2 (복사) 2,2,3 (붙여넣기) 4,2,4 (붙여넣기) 6,2,5 (복사) 6,6,6 (붙여넣기) 12,6,7 (붙여넣기) 18,6,8
3. 알고리즘
필요 변수
- 목표 이모티콘의 개수
int S(2 ≤ S ≤ 1000) - 현재 이모티콘의 개수
int N(2 ≤ S ≤ 1000) - 큐에 넣을 구조체
- 현재 스크린 개수
- 현재 클립보드에 들고있는 개수
- 현재 시간
int visited[screen][clipboard]screen 개의 이모티콘이 화면에 있고 clipboard 개의 이모티콘이 클립보드에 있는 상태가 있었는지 체크
특이하게 visited 베열을 2차원으로 사용한다. 잘 기억해두기
알고리즘
술래잡기 문제와 비슷하게 BFS를 이용하여 초를 계산한다
이모티콘의 개수를 바꿀 수 있는 경우의 수는 붙여넣기, 하나 삭제 총 3가지
1
2
3
4
5
6
7
8
9
10
11
12
1. S 입력받기
2. BFS 초기 세팅 {N, 0, 0} 을 큐에 집어넣는다
3. N 방문처리
4. BFS 시작
4-1. 큐에서 꺼내기
4-2. N 과 S가 같은지 비교
- 같다면 현재 시간을 출력 후 종료
4-3. 연산1, 2, 3중 하나 선택
4-3-1. 연산1) 현재 화면 복사 -> 클립보드에 기록 {N, N, 시간 + 1} // 클립보드에 N개로 수정됨
4-3-2. 연산2) 화면에 붙여넣기 -> 스크린 증가 {N + N, N, 시간 + 1} // 스크린에 N개만크 추가됨
4-3-3. 연산3) 화면에서 한글자 삭제 -> 화면 1 감소 {N -1, N, 시간 + 1} // 화면1 감소, 클립보드 그대로
4-3-4. 변경된 내용을 큐에 넣는다
주의사항
화면에 아무것도 없는데 삭제하는 경우나 복사를 시도하는 경우
혹은 계속 영원히 복사만 시도하는 경우 메모리 초과가 날 수 있으므로 주의할 것
4. 소스코드
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
#include <iostream>
#include <queue>
using namespace std;
int visited[1001][1001]; // 화면 개수, 클립보드 개수
struct node {
int screen;
int clipboard;
int second;
};
int main() {
int N = 1, S;
cin >> S;
queue<node> qu;
qu.push({ N, 0, 0 });
visited[N][0] = 1;
while (!qu.empty()) {
node now = qu.front();
qu.pop();
if (now.screen == S) {
cout << now.second;
return 0;
}
// 연산 1. 클립보드에 복사하는 경우
if (now.screen > 0 && now.screen < 1001 && visited[now.screen][now.screen] == 0) {
visited[now.screen][now.screen] = 1;
qu.push({ now.screen, now.screen, now.second + 1 });
}
// 연산 2. 화면에 붙여넣기하는 경우
int next;
next = now.screen + now.clipboard;
if (now.clipboard != 0 && next < 1001 && visited[next][now.clipboard] == 0) {
visited[next][now.clipboard] = 1;
qu.push({ next, now.clipboard, now.second + 1 });
}
// 연산 3. 화면에서 하나 삭제하는 경우
next = now.screen - 1;
if (next >= 0 && visited[next][now.clipboard] == 0) {
visited[next][now.clipboard] = now.second;
qu.push({ now.screen - 1, now.clipboard, now.second + 1 });
}
}
return 0;
}
visited 배열을 2차원으로 사용하는것이 잘 이해가 되지 않아 애먹었다.
visited 배열을 1차원으로 저장하여 방문했다면 1, 아직 안했다면 0으로 둘 경우 다음과 같은 문제가 생긴다
큐에 {8,4,6}, {6,6,5}가 순서대로 있다면
{8,4,6}이 큐에서 먼저 나와서 스크린에 8개, 클립보드의 4개를 붙여넣기하여 visited[12] = 1로 표시를 한뒤에 큐에 {12,4,7}을 집어넣게 된다
그러나 이는 최단거리가 아닌데 저장된 경우다.
{6,6,5}를 큐에서 뽑아 스크린에 6개, 클립보드의 6개를 붙여넣기한 {12,6,6}이 더 짧은 경우이므로 이를 체크하는 과정이 필요하다
visited를 2차원으로 다루면
{8,4,6}은 visited[8][4]를 방문체크하고, {6,6,5}는 visited[6][6]을 방문체크하여 최단거리를 체크할 수 있다
그렇다면 visited[6][6]은 언제 체크하게 될까?
{6, 2, 5}일때, 복사를 시도하면 클립보드가 6로 변경되므로, vistied[6][6]을 방문체크한다
이는 {6,6,5}에서 미리 1로 체크를 했으므로 이떄의 초 값이 5로 1초 더 빠르므로
{6,2,5}에서 클립보드에 복사하고 1초 경과한 {6,6,6}을 큐에 넣지 않고 패스한다
S=18일때 실행 결과를 보면
클립보드의 내용이 6일때, 9일때 18에 도달할 수 있는걸 볼 수 있다
큐에는 더 짧은 기록이 먼저 저장되기 때문에 가장 먼저 S와 일치하는 노드가 최단거리임을 알 수 있다