Home / 알고리즘 / DFS

백준 적록색약 10026번

11/20/2024

#알고리즘 #DFS

문제 해결 접근 방법

링크

백준-적록색약 10026

이 문제는 일반적인 사람과 적록색약인 사람이 그림을 보는 방식의 차이를 고려하여 두 가지 경우의 영역의 수를 구하는 문제이다.

문제 이해

그림은 N x N 크기의 격자로 주어지며, 각 칸은 'R', 'G', 'B' 중 하나의 색으로 채워져 있다.
일반적인 사람은 세 가지 색을 모두 구분할 수 있지만, 적록색약인 사람은 'R'과 'G'를 같은 색으로 인식한다.
두 가지 경우에 대해 각각의 연결된 같은 색 영역의 수를 구해야 한다.

그래프 탐색

DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용하여 연결된 영역을 찾는다.
두 번의 탐색이 필요하다. 하나는 일반적인 경우, 다른 하나는 적록색약인 경우이다.

구현 단계

입력을 받아 N x N 배열로 저장한다.
두 개의 방문 배열을 사용하여 각각의 경우에 대해 방문 여부를 기록한다.
DFS 또는 BFS를 통해 각 칸에서 시작하여 연결된 같은 색 영역을 탐색하고 카운트한다.

Node.js 구현 예시

아래는 Node.js로 구현한 예시 코드이다. 이 코드는 DFS를 사용하여 문제를 해결한다.

const BAEAKJOONFILE = "/dev/stdin";
const VSCODEFILE = "./coding/example.txt";

const fs = require('fs');
const input = fs.readFileSync(VSCODEFILE).toString().trim().split('\n');

const N = parseInt(input[0]);
const picture = input.slice(1).map(line => line.split(''));

const directions = [
	[0, 1], [1, 0], [0, -1], [-1, 0]
];

function isValid(x, y) {
	return x >= 0 && x < N && y >= 0 && y < N;
}

function dfs(x, y, color, visited, isColorBlind) {
	const stack = [[x, y]];
	visited[x][y] = true;

	while (stack.length > 0) {
		const [cx, cy] = stack.pop();
		
		for (const [dx, dy] of directions) {
			const nx = cx + dx;
			const ny = cy + dy;

			if (isValid(nx, ny) && !visited[nx][ny]) {
				if (isColorBlind) {
					if ((color === 'R' || color === 'G') && (picture[nx][ny] === 'R' || picture[nx][ny] === 'G')) {
						visited[nx][ny] = true;
						stack.push([nx, ny]);
					} else if (color === 'B' && picture[nx][ny] === 'B') {
						visited[nx][ny] = true;
						stack.push([nx, ny]);
					}
				} else {
					if (picture[nx][ny] === color) {
						visited[nx][ny] = true;
						stack.push([nx, ny]);
					}
				}
			}
		}
	}
}

function countRegions(isColorBlind) {
	const visited = Array.from({ length: N }, () => Array(N).fill(false));
	let regionsCount = 0;

	for (let i = 0; i < N; i++) {
		for (let j = 0; j < N; j++) {
			if (!visited[i][j]) {
				dfs(i, j, picture[i][j], visited, isColorBlind);
				regionsCount++;
			}
		}
	}
	return regionsCount;
}

const normalCount = countRegions(false);
const colorBlindCount = countRegions(true);

console.log(normalCount + " " + colorBlindCount);

이 코드는 입력을 받아 그림을 저장한 후 두 번의 DFS 탐색을 통해 일반적인 경우와 적록색약인 경우 각각의 영역 수를 계산한다. countRegions 함수는 isColorBlind 플래그에 따라 탐색 방식을 다르게 하여 두 가지 경우를 처리한다.

부분 설명

입력 처리

const fs = require('fs');
const input = fs.readFileSync(VSCODEFILE).toString().trim().split('\n');

const N = parseInt(input[0]);
const picture = input.slice(1).map(line => line.split(''));

이 부분은 입력을 받아 처리한다.

fs 모듈을 사용하여 표준 입력(/dev/stdin)에서 데이터를 읽어온다.
첫 번째 줄에서 N(그림의 크기)을 가져온다.
나머지 줄들을 2차원 배열 picture로 변환한다.

방향 설정 및 유효성 검사 함수

const directions = [
	[0, 1], [1, 0], [0, -1], [-1, 0]
];

function isValid(x, y) {
	return x >= 0 && x < N && y >= 0 && y < N;
}

directions는 상하좌우 이동을 위한 배열이다.
isValid 함수는 주어진 좌표가 그림 내(정해진 범위 내)에 있는지 확인한다.

DFS 함수

function dfs(x, y, color, visited, isColorBlind) {
	const stack = [[x, y]];
	visited[x][y] = true;

	while (stack.length > 0) {
		const [cx, cy] = stack.pop();
		
		for (const [dx, dy] of directions) {
			const nx = cx + dx;
			const ny = cy + dy;

			if (isValid(nx, ny) && !visited[nx][ny]) {
				if (isColorBlind) {
					if ((color === 'R' || color === 'G') && (picture[nx][ny] === 'R' || picture[nx][ny] === 'G')) {
						visited[nx][ny] = true;
						stack.push([nx, ny]);
					} else if (color === 'B' && picture[nx][ny] === 'B') {
						visited[nx][ny] = true;
						stack.push([nx, ny]);
					}
				} else {
					if (picture[nx][ny] === color) {
						visited[nx][ny] = true;
						stack.push([nx, ny]);
					}
				}
			}
		}
	}
}

이 함수는 깊이 우선 탐색(DFS)을 구현한다.

스택을 사용하여 반복적 DFS를 구현한다.
isColorBlind 매개변수에 따라 색 구분 로직이 달라진다.
적록색약인 경우, 'R'과 'G'를 같은 색으로 처리한다.

영역 카운팅 함수

function countRegions(isColorBlind) {
	const visited = Array.from({ length: N }, () => Array(N).fill(false));
	let regionsCount = 0;

	for (let i = 0; i < N; i++) {
		for (let j = 0; j < N; j++) {
			if (!visited[i][j]) {
				dfs(i, j, picture[i][j], visited, isColorBlind);
				regionsCount++;
			}
		}
	}
	return regionsCount;
}

이 함수는 전체 그림을 순회하며 영역의 수를 세는 역할을 한다.

방문하지 않은 칸을 발견하면 DFS를 시작하고 영역 수를 증가시킨다.
isColorBlind 매개변수로 일반인과 적록색약인 경우를 구분한다.

결과 출력

const normalCount = countRegions(false); 
const colorBlindCount = countRegions(true); 

console.log(normalCount + " " + colorBlindCount);

일반인의 경우와 적록색약인 경우 각각에 대해 countRegions 함수를 호출한다.
두 결과를 공백으로 구분하여 출력한다.

DFS 사용 이유

DFS(깊이 우선 탐색)를 사용하여 "적록색약" 문제를 해결한 이유는,

메모리 효율성: DFS는 스택을 사용하므로 BFS(너비 우선 탐색)에 비해 일반적으로 메모리 사용량이 적다. 이 문제에서는 그래프의 크기가 크기 않아 큰 차이는 없지만, 대규모 그래프에서는 이점이 될 수 있다.
구현의 간단함: DFS는 재귀적으로 구현하기 쉽다. 이 문제에서는 반복적 DFS를 사용했지만, 재귀적 구현도 가능하며 코드가 더 간결해질 수 있다.
연결된 영역 탐색: 이 문제는 연결된 색상 영역을 찾는 것이 목적이다. DFS는 한 영역을 완전히 탐색한 후 다음 영역으로 넘어가는 특성이 있어, 이런 유형의 문제에 적합하다.
최단 경로 불필요: BFS는 최단 경로를 찾는 데 유용하지만, 이 문제에서는 단순히 연결된 영역의 수만 필요하므로 시간 복잡도는 동일하다.
성능 차이 미미: 이 문제에서는 BFS와 DFS의 성능 차이가 크지 않다. 모든 노드를 방문해야 하므로 시간 복잡도는 동일하다.

결론적으로, DFS를 선택한 것은 구현의 간단함과 문제의 특성(연결된 영역 찾기)에 잘 맞기 때문이다. 하지만 BFS로도 충분히 해결 가능한 문제이며, 실제로 큰 차이는 없다.

블로그 내 관련 문서

참고 자료

출처 :

FromTo World

탐색기