문제
BOJ 14226 : 이모티콘 - https://www.acmicpc.net/problem/14226
풀이
화면에 이모티콘이 1개 입력되어 있다. 여기서 행할 수 있는 작업은 3가지.
1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.추가 조건)
- 모든 연산은 1초가 걸린다.
- 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다.
- 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다.
- 클립보드에 있는 이모티콘 중 일부를(일부만은) 삭제할 수 없다.
- 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.복/붙/삭제 3가지 작업을 적절하게 잘 섞어서 S개의 이모티콘을 화면에 만드는데 걸리는 최소 시간을 구한다.
우선 잘 생각해보면, 어떠한 한 상태 (예를 들어, 이모티콘이 화면에 1개 입력되어있는 상태)에서 할 수 있는 작업이 총 3가지이다. "복사/붙혀넣기/삭제"
이 3가지 작업들 중에선 가능한 작업도 있고, 불가능한 작업도 있다 (클립보드에 아무것도 없으면 붙혀넣기가 불가능한 것처럼). 그래서 현재 화면의 이모티콘 수, 클립보드에 저장되어있는 이모티콘 수 등을 확인하여 가능한 작업들을 하나하나 실행해보면 된다. => BFS 탐색으로 풀이하면 된다. 현재 상태에서 가능한 작업에 대해 큐에 넣고, 하나씩 빼서 또 그 상태에서 가능한 작업을 큐에넣고, ... 와 같이 반복하면 된다. 하나의 상태는 Step 클래스를 생성해서 화면의 이모티콘 수, 클립보드의 이모티콘 수, 시간 정보를 표현했다.
여기서 '모든' 상태에 대해 BFS를 실행한다면 이미 확인한 상태를 다시 확인하는 경우가 생긴다. 화면의 이모티콘 개수가 4이고 클립보드에 있는 이모티콘 개수가 2이고 시간은 4인 상태 가 있다고 해보자. 여기서 1번 붙혀넣고 삭제를 2번 하는 작업을 수행했다면, 화면의 이모티콘 개수가 4이고 클립보드에 있는 이모티콘 개수가 2이고 시간은 7인 상태 가 된다. 화면과 클립보드의 이모티콘 개수는 같지만 시간은 늘어나있다. 이것처럼 이미 확인했던 [화면 이모티콘 개수][클립보드의 이모티콘 개수]의 쌍을 다시 본다면 시간이 늘어나기 때문에 최솟값을 찾을 수 없다. 그래서 방문 여부를 체크해주기 위해 boolean[][] visited 와 같이 이중 배열을 사용한다. (여기서 행은 화면 이모티콘 개수, 열은 클립보드의 이모티콘 개수)
방문 여부를 확인할 때는,
- 복사 : visited[화면의 이모티콘 수][화면의 이모티콘 수]를 확인한다. 복사를 수행했을 경우 이전 꺼는 덮어씌워지기 때문에 화면의 이모티콘 수와 클립보드의 이모티콘 수가 같아진다.
- 붙혀넣기 : visited[화면의 이모티콘 수+클립보드의 이모티콘 수][클립보드의 이모티콘 수]를 확인한다. 붙혀넣기를 수행하면 화면 이모티콘 수에 클립보드 이모티콘 개수가 더해진다.
- 삭제 : visited[화면의 이모티콘 수-1][클립보드의 이모티콘 수]를 확인한다.
배열 범위를 2000까지 한거는 원래 화면에 있던 개수(최대 1000) + 붙혀넣기 가능한 개수(최대 1000) 해서 최대 2000으로 범위를 잡는다. (다른 분 블로그에서 참고한건데 사실 이거는 아직도 이해가 잘 안된다..ㅠㅠ)
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static class Step{
int emoticon_num;
int clipboard_num;
int time;
public Step(int emoticon_num, int clipboard_num, int time) {
this.emoticon_num = emoticon_num;
this.clipboard_num = clipboard_num;
this.time = time;
}
}
static boolean[][] visited;
static int S;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
S = Integer.parseInt(br.readLine());
visited = new boolean[2001][2001]; // 행: 화면 이모티콘의 개수, 열:클립보드 이모티콘 개수
bfs();
}
public static void bfs() {
Queue<Step> queue = new LinkedList<>();
queue.add(new Step(1, 0, 0));
while (!queue.isEmpty()) {
Step now = queue.poll();
int emoticon_num = now.emoticon_num;
int clipboard_num = now.clipboard_num;
int time = now.time;
if(emoticon_num == S){
System.out.println(time);
return;
}
if(emoticon_num > 0 && emoticon_num < 2000){
// 1. 복사
if(!visited[emoticon_num][emoticon_num]){
visited[emoticon_num][emoticon_num] = true;
queue.offer(new Step(emoticon_num, emoticon_num, time + 1));
}
// 3. 삭제
if (!visited[emoticon_num - 1][clipboard_num]) {
visited[emoticon_num - 1][clipboard_num] = true;
queue.offer(new Step(emoticon_num - 1, clipboard_num, time + 1));
}
}
// 2. 붙여넣기
if (clipboard_num > 0 && emoticon_num + clipboard_num < 2000) {
if (!visited[emoticon_num+clipboard_num][clipboard_num]) {
visited[emoticon_num+clipboard_num][clipboard_num] = true;
queue.offer(new Step(emoticon_num + clipboard_num, clipboard_num, time + 1));
}
}
}
}
}
정리
✔ 알고리즘 분류 - 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색
✔ 난이도 - 🟡 Gold 5🤦♀️ 오늘의 메모
-
체감상 Gold 1~3정도 되는 난이도였다. DP문제에 특히 약하긴 한데 이번 문제는 어떻게 해야할 지 감도 안잡혔던 터라 구글링으로 겨우겨우 이해했다.
아니 도대체 문제만 보고 이중배열로 visited 처리 할지를 어떻게 생각하냐구.memorization을 어떻게 해야할 지 많이 연습해봐야겠다. -
일단
여러 선택지(?)가 나오는데 최솟값을 구해야한다!하면 BFS풀이를 의심해보자.
참고 사이트
https://daily-life-of-bsh.tistory.com/68
https://iamheesoo.github.io/blog/algo-boj14226
