돌 그룹

문제

백준 12886번 - 돌 그룹

언어

JavaScript

순서도

BFS 탐색

문제 풀이 step 1

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 합니다.
돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C 개가 있습니다.
강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 합니다.
강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있습니다.
- 크기가 같지 않은 두 그룹을 고릅니다.
- 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y 라고 정합니다.
- 그 다음, X 에 있는 돌의 개수를 X + X 개로, Y 에 있는 돌의 개수를 Y - X 개로 만듭니다.
A, B, C 가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1 을, 아니면 0 을 출력하는 문제입니다.

문제 풀이 step 2

3 차원 공간에 시작점 (a, b, c) 를 하나의 노드로 생각합니다.
그리고 돌을 움직이는 규칙에 따라서 BFS 탐색을 합니다.
- 탐색을 할 때 방문 처리를 해야하는데, 3 차원 배열을 생성하면 메모리 초과가 발생합니다.
- 따라서 Map 을 이용해서 방문 처리를 하고, (a, b, c) 를 적절히 문자열로 변환 후 key 값으로 사용합니다.
BFS 탐색을 모두 마치면 세 개의 돌이 같아지는 순간이 있는 지 검사하고, 있다면 1 을, 없다면 0 을 출력합니다.
추가 설명은 주석으로 작성하겠습니다.

후기

꼭 다시 풀어볼 문제입니다.
처음에는 무지성으로 문제를 풀었더니 메모리와 소요시간이 너무 크게 발생했습니다.
그래서 분석하고 공부 후 다시 풀어봤습니다.
문제를 풀 때, 무지성을 지양하고, 문제를 수학적으로 분석하고 풀어야 할 것 같습니다.

소스 코드

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

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

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

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

const bfs = (a, b, c) => {
	const queue = new Queue();
	// Map 을 이용해서 방문처리
	const visitedMap = new Map();

	if (a === b && b === c) return true;

	queue.enqueue([a, b, c]);
	visitedMap.set([a, b, c].join(" "), true);

	while (!queue.isEmpty()) {
		const [x, y, z] = queue.dequeue();
		const next = [];

		// 규칙에 맞게 다음 탐색 노드 결정
		if (x !== y) {
			if (x < y) {
				next.push([x + x, y - x, z]);
			} else {
				next.push([x - y, y + y, z]);
			}
		}

		if (x !== z) {
			if (x < z) {
				next.push([x + x, y, z - x]);
			} else {
				next.push([x - z, y, z + z]);
			}
		}

		if (y !== z) {
			if (y < z) {
				next.push([x, y + y, z - y]);
			} else {
				next.push([x, y - z, z + z]);
			}
		}

		for (let i = 0; i < next.length; i++) {
			const [nx, ny, nz] = next[i];
			const key = next[i].join(" ");

			// 이미 방문 했다면 SKIP
			if (visitedMap.get(key) === true) continue;
			if (nx === ny && ny === nz) return true;

			// 방문 처리
			visitedMap.set(key, true);
			queue.enqueue([nx, ny, nz]);
		}
	}

	return false;
};

const solution = (input) => {
	const [a, b, c] = input[0].split(" ").map(Number);

	const result = bfs(a, b, c);

	if (result === true) return 1;
	return 0;
};

console.log(solution(input));

다른 방식의 문제 풀이 step 1

중요한 포인트
- 3 개의 그룹의 돌의 개수의 합은 변하지 않습니다.
- 문제에서 주어진 단계를 보면 돌이 그룹 안에서만 이동을 하기 때문에 전체적인 돌의 개수는 변하지 않습니다.
개선점
- 3 개의 수가 같은 수가 되려면, 이 수들의 합이 3 의 배수여야 합니다.
  - 너무 당연한 건데 문제를 풀 때는 본 내용이 잘 보이진 않습니다.
  - 따라서, 초기에 각 그룹에 있는 돌의 개수를 모두 더한 값이 3 의 배수인지 확인해줍니다.
- 각 돌 그룹을 구분할 필요가 없습니다.
  - 따라서, 매 단계마다 돌을 오름차순으로 정렬 후에 로직을 전개해도 됩니다.
  - 정렬을 하게 되면, 돌의 개수가 작은 쪽과 큰 쪽을 구분하기 쉬워집니다.
- 방문처리를 2 차원 배열로 해도 무방합니다.
  - 오름차순으로 정렬하게 되면 가장 작은 돌의 개수와 그 다음으로 큰 돌의 개수만 방문처리를 해도 됩니다.
  - 왜냐하면, 전체적인 돌의 개수가 고정되어 있기에 두 개로 나머지 하나를 결정할 수 있기 때문입니다.
이런 개선점을 적용한 소스 코드를 아래에 작성합니다.

다른 방식의 소스 코드

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

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

	enqueue(item) {
		this.bucket[++this.rear] = item;
	}

	dequeue() {
		return this.bucket[++this.front];
	}

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

const bfs = (a, b, c) => {
	const queue = new Queue();
	// 2 차원 배열로 방문처리
	const visited = Array.from({length: 1501}, () => Array(1501).fill(false));

	queue.enqueue([a, b, c]);
	visited[a][b] = true;

	while (!queue.isEmpty()) {
		const [x, y, z] = queue.dequeue();
		const next = [];

		// 정렬했으니 대소 비교는 이미 되어있는 상태
		if (x !== y) next.push([x + x, y - x, z].sort((a, b) => a - b));
		if (x !== z) next.push([x + x, y, z - x].sort((a, b) => a - b));
		if (y !== z) next.push([x, y + y, z - y].sort((a, b) => a - b));

		for (let i = 0; i < next.length; i++) {
			const [nx, ny, nz] = next[i];

			// 2 차원으로 방문처리
			if (visited[nx][ny] === true) continue;
			if (nx === ny && ny === nz) return 1;

			visited[nx][ny] = true;
			queue.enqueue([nx, ny, nz]);
		}
	}

	return 0;
};

const solution = (input) => {
	const [a, b, c] = input[0]
		.split(" ")
		.map(Number)
		.sort((a, b) => a - b);

	// 각 그룹의 돌의 합은 변하지 않으므로, 3 의 배수인지 검사
	if ((a + b + c) % 3 !== 0) return 0;
	if (a === b && b === c) return 1;

	const result = bfs(a, b, c);
	return result;
};

console.log(solution(input));