[BOJ/BFS] 백준 14226 - 이모티콘 (Java)

14226 - 이모티콘

https://www.acmicpc.net/problem/14226

문제

3가지 연산만을 사용해서 이모티콘 S개를 만들어 보내려 함
1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 함
3. 화면에 있는 이모티콘 중 하나 삭제
모든 연산은 1초가 걸리고 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 됨
클립보드가 비어있는 상태에는 붙여넣기 X / 일부만 클립보드에 복사 X / 클립보드에 있는 이모티콘 중 일부 삭제 X
화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가

=> 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램?

입력: S (2 <= S <= 1000)
출력: 이모티콘 S를 만들기 위해 필요한 시간의 최솟값

---

풀이

• 현재 화면에 있는 이모티콘 수, 클립보드에 복사된 이모티콘 수, 지금까지 거린 시간 클래스

class State {
    int screen, clipboard, time;

    public State(int screen, int clipboard, int time) {
        this.screen = screen;
        this.clipboard = clipboard;
        this.time = time;
    }
}

 

• `visited[screen][clipboard]`: 화면 수와 클립보드 수의 조합은 상태 공간 -> 중복 방문 방지

 

BFS

• 화면에 이모티콘 1개, 클립보드 0개, 시간 0초로 시작
  • (1, 0) 상태 방문 처리
• 화면에 이모티콘 S개 -> `cur.time` 출력 후 종료

if (cur.screen == S) {
    System.out.println(cur.time);
    return;
}

• 복사: 화면 -> 클립보드
  • 조건: 화면의 개수만큼 클립보드에 복사
    • `cur.screen < MAX`: 화면에 있는 이모티콘 수 < 최대 범위
    • `!visited[cur.screen][cur.screen]`: 이 (화면, 클립보드) 상태 처음 방문
  • 결과: 클립보드 업데이트, 화면 그래로
    • 클립보드에 현재 화면 개수만큼 복사
    • 화면 그대로 유지

if (cur.screen < MAX && !visited[cur.screen][cur.screen]) {
    visited[cur.screen][cur.screen] = true;
    q.offer(new State(cur.screen, cur.screen, cur.time + 1));
}

• 붙여넣기: 클립보드 -> 화면 추가
  • 조건: 클립보드에 뭔가 있어야 함
    • `cur.clipboard > 0`: 클립보드에 이모티콘 O (-> 붙여넣기 가능)
    • `cur.screen + cur.clipboard < MAX`: 총 이모티콘 수 < 최대 범위
    • `!visited[cur.screen + cur.clipboard][cur.clipboard]`: 이 상태 처음 방문
  • 결과: 화면 += 1
    • 화면에 클립보드 개수만큼 이모티콘 추가
    • 클립보드 그대로 유지

if (cur.clipboard > 0 && cur.screen + cur.clipboard < MAX && !visited[cur.screen + cur.clipboard][cur.clipboard]) {
    visited[cur.screen + cur.clipboard][cur.clipboard] = true;
    q.offer(new State(cur.screen + cur.clipboard, cur.clipboard, cur.time + 1));
}

• 삭제: 화면에서 하나 빼기
  • 조건: 화면에 이모티콘 최소 1개
    • `cur.screen > 0`: 화면에 이모티콘 O (-> 삭제 가능)
    • `!visited[cur.screen - 1][cur.clipboard]`: 이 상태 처음 방문
  • 결과: 화면 -= 1
    • 화면에서 이모티콘 1개 삭제 
    • 클립보드 그대로 유지

if (cur.screen > 0 && !visited[cur.screen - 1][cur.clipboard]) {
    visited[cur.screen - 1][cur.clipboard] = true;
    q.offer(new State(cur.screen - 1, cur.clipboard, cur.time + 1));
}

---

예시

S = 6 / 초기 상태: (screen = 1, clipboard = 0, time = 0)

• 복사
  • 현재 상태: (1, 0, 0)
  • 복사 -> clipboard = screen = 1
  • 다음 상태: (1, 1, 1)
• 붙여넣기
  • 현재 상태: (1, 1, 1)
  • 붙여넣기 -> screen = 1 + 1 = 2
  • 다음 상태: (2, 1, 2)
• 붙여넣기
  • 현재 상태: (2, 1, 2)
  • 붙여넣기 -> screen = 2 + 1 = 3
  • 다음 상태: (3, 1, 3)
• 복사
  • 현재 상태: (3, 1, 3)
  • 복사 -> clipboar = 3
  • 다음 상태: (3, 3, 4)
• 붙여넣기
  • 현재 상태: (3, 3, 4)
  • 붙여넣기 -> screen = 3 + 3 = 6
  • 다음 상태: (6, 3, 5) 

=> 5

---

코드

import java.io.*;
import java.util.*;

// 이모티콘
class State {
    int screen, clipboard, time;

    public State(int screen, int clipboard, int time) {
        this.screen = screen;
        this.clipboard = clipboard;
        this.time = time;
    }
}

public class boj_14226 {
    static int S;
    static final int MAX = 2001;
    static boolean[][] visited = new boolean[MAX][MAX];

    static void bfs() {
        Queue<State> q = new LinkedList<>();
        q.offer(new State(1, 0, 0));
        visited[1][0] = true;

        while (!q.isEmpty()) {
            State cur = q.poll();

            if (cur.screen == S) {
                System.out.println(cur.time);
                return;
            }

            if (cur.screen < MAX && !visited[cur.screen][cur.screen]) {
                visited[cur.screen][cur.screen] = true;
                q.offer(new State(cur.screen, cur.screen, cur.time + 1));
            }

            if (cur.clipboard > 0 && cur.screen + cur.clipboard < MAX && !visited[cur.screen + cur.clipboard][cur.clipboard]) {
                visited[cur.screen + cur.clipboard][cur.clipboard] = true;
                q.offer(new State(cur.screen + cur.clipboard, cur.clipboard, cur.time + 1));
            }

            if (cur.screen > 0 && !visited[cur.screen - 1][cur.clipboard]) {
                visited[cur.screen - 1][cur.clipboard] = true;
                q.offer(new State(cur.screen - 1, cur.clipboard, cur.time + 1));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        S = Integer.parseInt(br.readLine());

        bfs();
    }
}