적록색약

문제

언어

  • JavaScript

순서도

  1. 주어진 격자에서 BFS 탐색을 통해서 구역의 개수 구하기
  2. 녹색을 적색으로 변환
  3. 변환된 격자에서 BFS 탐색을 통해서 구역의 개수 구하기

문제 풀이 step 1

  • 백준 2667번 - 단지 번호 붙이기 풀이 와 유사하게 BFS 탐색을 통해 풀 수 있습니다.
  • 크기가 N x N 인 그리드가 주어질 때, 적록색약인 사람과 적록색약이 아닌 사람 각각에 따라서 구역의 개수를 구하는 문제입니다.
    • 구역은 그리드에서 같은 색으로 이루어져 있는 부분을 말합니다.
    • 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못합니다.
  • 우선, 적록색약이 아닌 사람 입장에서 구역의 개수를 구합니다.
    • 이는 BFS 탐색을 하며, 처음 탐색을 시작한 위치의 색과 동일한 색인 칸만 탐색하는 방법을 통해서 구할 수 있습니다.
  • 그리고 그리드에서 초록색을 빨간색으로 또는 빨간색을 초록색으로 변환합니다.
  • 그리고 적록색약인 사람 입장에서 구역의 개수를 구합니다.
    • 이를 위해서, 위에서 그리드에서 초록색과 빨간색을 구분할 수 없도록 같은 색으로 변환했습니다.
    • 이번에도 마찬가지로 BFS 탐색을 하며, 처음 탐색을 시작한 위치의 색과 동일한 색의 칸만 탐색하는 방법을 통해서 구합니다.
  • 구한 구역의 개수를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드

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

class Dot {
	constructor(x, y) {
		this.x = x;
		this.y = y;
	}
}

// 간단한 Queue 구현
class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

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

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

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

// 다음에 탐색할 칸이 격자를 벗어나지 않는지 검사
const isPossibleRoute = (n, to) =>
	0 <= to.x && to.x < n && 0 <= to.y && to.y < n;

// BFS 탐색
const bfs = (n, grid, visited, x, y) => {
	// 상, 하, 좌, 우
	const cx = [0, 0, 1, -1];
	const cy = [1, -1, 0, 0];

	const queue = new Queue();
	queue.enqueue(new Dot(x, y));
	visited[x][y] = true;

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

		for (let i = 0; i < 4; i++) {
			const to = new Dot(from.x + cx[i], from.y + cy[i]);

			if (!isPossibleRoute(n, to)) continue;
			if (visited[to.x][to.y]) continue;
			// 시작점과 동일한 색의 칸만 탐색 진행
			if (grid[to.x][to.y] !== grid[from.x][from.y]) continue;

			visited[to.x][to.y] = true;
			queue.enqueue(to);
		}
	}
};

const solution = (input) => {
	const n = Number(input[0]);
	const grid = input.slice(1, n + 1).map((v) => v.split(""));

	// 우선, 적록색약이 아닌 사람 입장에서 구역의 개수 구하기
	let normalCnt = 0;
	let visited = Array.from({length: n}, () => Array(n).fill(false));
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (visited[i][j]) continue;

			bfs(n, grid, visited, i, j);
			normalCnt += 1;
		}
	}

	// 빨간색과 초록색을 구분할 수 없도록 같은색으로 변환
	const newGrid = grid.map((v) => v.map((v) => (v === "G" ? "R" : v)));

	// 적록색약인 사람 입장에서 구역의 개수 구하기
	let blindCnt = 0;
	visited = Array.from({length: n}, () => Array(n).fill(false));
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (visited[i][j]) continue;

			bfs(n, newGrid, visited, i, j);
			blindCnt += 1;
		}
	}

	return normalCnt + " " + blindCnt;
};

console.log(solution(input));