백준 14226번: 이모티콘

문제

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

14226번: 이모티콘

---

풀이

화면에 이모티콘 1개가 입력되어 있는 상태인 영선이가 효빈이에게 다음 규칙에 맞춰 이모티콘을 s개 보내야 하는 문제입니다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸리고 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 됩니다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며 일부만 클립보드에 복사할 수는 없고, 또한 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없을 때 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 문제입니다.

---

접근

2차원 boolean 배열 visitited[screen][clipboard]를 만듭니다. screen은 현재 화면에 있는 이모티콘의 개수, clipboard는 클립보드에 있는 이모티콘의 개수를 의미합니다. s의 범위가 2 <= s <= 1000이므로 s가 1000일 경우의 수를 생각했을 때 화면에 1002개의 이모티콘을 만들고 2개를 지우는 것보다 1000개의 이모티콘을 바로 만드는 것이 빠르다고 생각됐기 때문에 visited의 크기를 [1001][1001]로 설정했습니다.

이 문제에서 BFS에 사용되는 큐에 들어가는 노드의 정보는 screen, clipboard 뿐만 아니라 현재 상태까지 걸린 시간의 최솟값인 time이 추가된 emoticon 클래스를 만들어서 사용했습니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;

class emoticon {
    int screen, clipboard, time;

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

public class Main {

    static boolean[][] visited = new boolean[1001][1001];

    public static void bfs(int s) {
        Queue<emoticon> queue = new LinkedList<emoticon>();
        queue.offer(new emoticon(1, 0, 0)); // (1)
        visited[1][0] = true;
        while (!queue.isEmpty()) {
            emoticon e = queue.poll(); // (2)
            if (e.screen == s) { // (3)
                System.out.println(e.time);
                System.exit(0);
            }
            if (!visited[e.screen][e.screen]) { // copy
                queue.offer(new emoticon(e.screen, e.screen, e.time + 1));
                visited[e.screen][e.screen] = true;
            }
            if (e.clipboard != 0 && e.screen + e.clipboard <= 1000 && !visited[e.screen + e.clipboard][e.clipboard]) { // paste
                queue.offer(new emoticon(e.screen + e.clipboard, e.clipboard, e.time + 1));
                visited[e.screen + e.clipboard][e.clipboard] = true;
            }
            if (e.screen > 0 && !visited[e.screen - 1][e.clipboard]) { // delete
                queue.offer(new emoticon(e.screen - 1, e.clipboard, e.time + 1));
                visited[e.screen - 1][e.clipboard] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int s = Integer.parseInt(br.readLine());
        bfs(s);
    }
}

s를 입력받고 bfs 함수를 실행합니다.

 

(1) 큐에 emoticon(1, 0, 0)을 추가하고 visited[1][0]을 true로 초기화합니다.

초기 조건에서 1개의 이모티콘을 갖고 있고 클립보드는 비워져있다고 했기 때문입니다.

 

(2) 현재 상태를 의미하는 emoticon e

e가 할 수 있는 3가지 경우의 수는 아래와 같습니다.

 

(copy) 현재 화면에 있는 이모티콘의 개수만큼 클립보드에 복사합니다.

화면에 있는 이모티콘의 개수만큼 클립보드에 복사되기 때문에 큐에 emoticon(e.screen, e.screen, e.time + 1)을 추가합니다.  이때 클립보드에 있는 이모티콘의 개수가 화면에 있는 이모티콘의 개수보다 커질 수 없기 때문에 아무런 추가 조건이 필요하지 않으며 visited[e.screen][e.screen]을 true로 초기화합니다.

 

(paste) 현재 클립보드에 있는 이모티콘의 개수만큼 화면에 붙여넣습니다.

클립보드에 있는 이모티콘의 개수만큼 화면에 붙여넣게 되기 때문에 큐에 emoticon(e.screen + e.clipboard, e.clipboard, e.time + 1)을 추가해야 합니다. 이때 클립보드가 비어있으면 붙여넣기 기능을 실행할 수 없고 붙여넣은 뒤에 화면에 있는 이모티콘의 개수가 1000을 넘어갈 수 없으며 visited[e.screen + e.clipboard][e.clipboard]가 이미 true라면 가장 빠른 방법이 아니므로 추가 조건이 필요합니다. 모든 조건을 만족하면 visited[e.screen + e.clipboard][e.clipboard]을 true로 초기화합니다.

 

(delete) 현재 화면에 있는 이모티콘 중 1개를 삭제합니다.

큐에 emoticon(e.screen  - 1, e.clipboard, e.time + 1)을 추가해야 합니다. 이때 화면에 이모티콘이 1개밖에 없으면 1개를 삭제했을 때 0이 되며 복사 및 붙여넣기 기능밖에 없기 때문에 의미가 없으며 visited[e.screen - 1][e.clipboard]가 이미 true라면 가장 빠른 방법이 아니므로 추가 조건이 필요합니다. 모든 조건을 만족하면 visited[e.screen - 1][e.clipboard]을 true로 초기화합니다.

 

(3) e.screen이 s와 같은지 확인합니다.

같다면 e.cnt를 출력한 후 프로그램을 종료합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#define math_min(a, b) a < b ? a : b
int s, visited[1001][1001];
typedef struct {
	int screen, clipboard, time;
} Emoticon;
typedef struct node {
	Emoticon emoticon;
	struct node* next;
} node;
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int screen, int clipboard, int time) {
	node* now = (node*)malloc(sizeof(node));
	now->emoticon.screen = screen;
	now->emoticon.clipboard = clipboard;
	now->emoticon.time = time;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
Emoticon pop(Queue* queue) {
	Emoticon re;
	node* now;
	now = queue->front;
	re = now->emoticon;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
void bfs() {
	Queue queue;
	initQueue(&queue);
	push(&queue, 1, 0, 0);
	visited[1][0] = 1;
	while (!empty(&queue)) {
		Emoticon e = pop(&queue);
		if (e.screen == s) {
			printf("%d", e.time);
			exit(0);
		}
		if (!visited[e.screen][e.screen]) {
			push(&queue, e.screen, e.screen, e.time + 1);
			visited[e.screen][e.screen] = 1;
		}
		if (e.clipboard != 0 && e.screen + e.clipboard <= 1000 && !visited[e.screen + e.clipboard][e.clipboard]) {
			push(&queue, e.screen + e.clipboard, e.clipboard, e.time + 1);
			visited[e.screen + e.clipboard][e.clipboard] = 1;
		}
		if (e.screen > 0 && !visited[e.screen - 1][e.clipboard]) {
			push(&queue, e.screen - 1, e.clipboard, e.time + 1);
			visited[e.screen - 1][e.clipboard] = 1;
		}
	}
}
main() {
	scanf("%d", &s);
	bfs();
}

자바를 이용한 풀이와 동일합니다.

---

결론

최근에 종강한 후에 2023년 새해가 밝았고 여러 약속이 겹치고 자바 스프링 공부가 먼저라는 생각이 들어 따로 공부한다는 핑계로 블로그에 글 작성하는 것을 게을리했던 것 같습니다. 아무튼 위의 문제를 더 연구해 본다면 DP로도 풀 수 있을 것 같다는 생각이 들었는데 추후에 시간이 된다면 도전해 보고 싶습니다.