이모티콘

문제

백준 14226번 - 이모티콘

언어

JavaScript

순서도

BFS 탐색

문제 풀이 step 1

영선이는 3 가지 연산을 이용해서 이모티콘의 개수를 늘릴 수 있는데, 이 때 이모티콘 S 개를 만들기 위해 필요한 시간의 최솟값을 출력해야 합니다.
결론부터 말씀드리면, BFS 탐색을 이용해서 풀 수 있습니다.
우선 그래프를 1 차원 배열의 형태로 풀 수 없습니다. 왜냐하면 모든 노드마다 클립보드에 복사된 이모티콘의 개수마다 다른 노드로 볼 수 있기 때문입니다.
그래서 그래프의 한 노드는 아래와 같은 형태를 지니고 있습니다.
- node[count][clipboard]
- “이모티콘의 개수가 count개 이며, 클립보드에 복사된 이모티콘의 개수는 clipboard 개 인 노드” 를 의미합니다.
- 그럼 이렇게 2 차원의 형태로 풀 수 있는지 검증을 해봐야겠습니다.
- 주어지는 범위가 1000 이하이므로 1000 * 1000 = 1000000 으로 충분히 가능한 범위입니다.
그래서 그래프의 형태는 이모티콘의 개수와 클립보드에 복사된 개수 이 두 가지로 조합된 2 차원 배열 형태를 가지게됩니다.

문제 풀이 step 2

다음으로 BFS 탐색의 과정을 알아보겠습니다.
이 문제에서 다음 노드로 탐색하는 방법은 3 가지 있습니다.
1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장
  - arr[from.count][from.count]
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
  - arr[from.count + from.clipboard][from.clipboard]
3. 화면에 잇는 이모티콘 중 하나를 삭제
  - arr[from.count - 1][from.clipboard]
그리고 각 노드에 시간을 기록하는 방식으로 방문 처리를 대신했습니다.
- arr[from.count][from.count] = arr[from.count][from.clipboard] + 1;
그리고 클립보드에 복사된 개수가 몇 개이건 상관없이 이모티콘의 개수가 S 개인 노드가 하나라도 생기면 더이상의 탐색은 무의미합니다.
- if (from.count === s) return arr[from.count][from.clipboard];
- 모든 BFS 탐색을 끝내고, 나중에 이모티콘의 개수가 S 개인 모든 값들 중 최솟값을 찾는 과정으로 풀어야 할 것 같은데, 이렇게 해도 풀 수 있는 이유는 제가 생각하기에는 BFS 탐색의 시작점이 하나이기 때문이라고 생각합니다. (시작이 여러개의 반대)
- 그리고 시작점이 하나이기 때문에 이후로 탐색되는 이모티콘의 개수가 S 개인 노드는 처음 탐색된 값보다 같거나 그 이상의 값일 것입니다.

후기

꼭 다시 풀어볼 문제입니다.
이 문제의 가장 중요한 것은 1 차원 배열의 형태를 쥐어줬는데 그것을 2 차원의 형태로 바꿀 수 있느냐 없느냐 라고 생각합니다.
그리고 변수 명을 좀더 간결하게 축소화하는 것이 맞을까 라는 의문이 많이 들었습니다.
- 의미를 명확하게 주고 싶어서 변수명을 정직하게 줄이지 않고 사용을 했는데, 오히려 코드를 작성하는 것도 어렵고 가독성도 떨어지는 것 같습니다.
- 하지만 의미를 모호하게 주는 것보다는 낫다고 생각하지만, 해결점을 찾아야할 것 같습니다. (의미를 최대한 살리면서 줄여보는 방식으로)

소스 코드 1

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

class Dot {
	constructor(count, clipboard) {
		this.count = count;
		this.clipboard = clipboard;
	}
}

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	isEmpty() {
		return this.front === this.rear;
	}

	enqueue(data) {
		this.bucket[++this.front] = data;
	}

	dequeue() {
		if (!this.isEmpty()) return this.bucket[++this.rear];
	}
}

const BFS = (arr, s) => {
	const queue = new Queue();

	// 초기 이모티콘 1 개
	arr[1][0] = 0;
	queue.enqueue(new Dot(1, 0));

	while (!queue.isEmpty()) {
		const from = queue.dequeue();

		// 찾으면 더이상의 탐색은 의미없음 그래서 바로 return
		if (from.count === s) return arr[from.count][from.clipboard];

		// 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장
		if (arr[from.count][from.count] === undefined) {
			arr[from.count][from.count] = arr[from.count][from.clipboard] + 1;
			queue.enqueue(new Dot(from.count, from.count));
		}

		// 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기
		if (
			from.count + from.clipboard <= s &&
			arr[from.count + from.clipboard][from.clipboard] === undefined
		) {
			arr[from.count + from.clipboard][from.clipboard] =
				arr[from.count][from.clipboard] + 1;
			queue.enqueue(new Dot(from.count + from.clipboard, from.clipboard));
		}

		// 3. 화면에 있는 이모티콘 중 하나를 삭제
		if (
			0 <= from.count - 1 &&
			arr[from.count - 1][from.clipboard] === undefined
		) {
			arr[from.count - 1][from.clipboard] = arr[from.count][from.clipboard] + 1;
			queue.enqueue(new Dot(from.count - 1, from.clipboard));
		}
	}
};

const solution = (input) => {
	const s = parseInt(input[0]);
	const arr = Array.from({length: s + 1}, () => []);

	const min = BFS(arr, s);
	return min;
};

console.log(solution(input));