HERSTORY

[C++ 알고리즘] 백준 10026번 : 적록색약

  • 2021년 02월 02일


DFS BFS

적록색약

풀이과정

  1. 방향을 나타내는 배열을 만들어 상하좌우를 탐색한다.
  2. 입력받은 그림정보를 가공하여 적록색약인 사람에 대해 탐색한다.
    • 색깔이 G인 경우 R로 바꾸고 탐색
  3. 함수의 재귀를 이용해 DFS를 수행한다.


코드

#include <stdio.h>
#include <string.h>

using namespace std;

int n, cnt = 0;
char photo[100][100];
bool isVisited[100][100] = { false };

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

void dfs(int x, int y) {
	isVisited[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
		if (!isVisited[nx][ny] && photo[x][y] == photo[nx][ny]) {
			dfs(nx, ny);
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", photo[i]);
	}

	//적록색약이 아닌 사람
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!isVisited[i][j]) {
				dfs( i, j);
				cnt++;
			}
		}
	}
	printf("%d ", cnt);

	//적록색약인 사람
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (photo[i][j] == 'G') photo[i][j] = 'R';
			else photo[i][j] = photo[i][j];
		}
	}
	memset(isVisited, false, sizeof(isVisited));

	cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!isVisited[i][j]) {
				dfs(i, j);
				cnt++;
			}
		}
	}
	printf("%d", cnt);

	return 0;
}



검색