[백준] 10026번 적록색약 (C++, JAVA)

10026번: 적록색약

처음엔 두 가지의 버전의 BFS를 만들었다가

애초에 입력받을 때 R과 G를 통일을 해주면 BFS함수 하나만으로도 풀 수 있다는 걸 깨달았다.

이차원 배열 두 가지를 만들어 하나는 정상적으로, 하나는 R과 G를 R로 통일해준다.

 

BFS함수는 늘 짜던 그 방식으로 해주면 된다.

 

< C++ 코드 >

#include <iostream>
#include <queue>
using namespace std;

int daltonism = 0, non_daltonism = 0, x, y;
void Bfs(int i, int j, int N, char arr[][101]) {
	queue <pair<int, int>> q;
	q.push(pair<int, int>(i, j));
	char section = arr[i][j];
	arr[i][j] = '0';
	while (!q.empty()) {
		x = q.front().first, y = q.front().second;
		if (x - 1 >= 0 && arr[x - 1][y] == section) { //상
			q.push(pair<int, int>(x - 1, y));
			arr[x - 1][y] = '0';
		}
		if (x + 1 < N && arr[x + 1][y] == section) { //하
			q.push(pair<int, int>(x + 1, y));
			arr[x + 1][y] = '0';
		}
		if (y - 1 >= 0 && arr[x][y - 1] == section) { //좌
			q.push(pair<int, int>(x, y - 1));
			arr[x][y - 1] = '0';
		}
		if (y + 1 < N && arr[x][y + 1] == section) { //우
			q.push(pair<int, int>(x, y + 1));
			arr[x][y + 1] = '0';
		}
		q.pop();
	}
}

int main() {
	int N;
	cin >> N;
	char arr[101][101] = { 0 }, arr2[101][101] = { 0 };
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
		cin >> arr[i][j];
		if (arr[i][j] == 'G') arr2[i][j] = 'R';
		else  arr2[i][j] = arr[i][j];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j] != '0') {
				Bfs(i, j, N, arr);
				non_daltonism++;
			}
			if (arr2[i][j] != '0') {
				Bfs(i, j, N, arr2);
				daltonism++;
			}
		}
	}
	
	cout << non_daltonism << " " << daltonism;

	return 0;
}

 

< JAVA 코드 >

import java.util.Scanner;

public class BOJ_10026_적록색약 {
	private static int N;
	private static int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
	
	public static void dfs(int X, int Y, char ch, char arr[][], boolean visited[][]) {
		visited[X][Y] = true;
		for(int i = 0; i < 4; i++) {
			int x = X + dx[i], y = Y + dy[i];
			if(x < 0 || x >= N || y < 0 || y >= N || arr[x][y] != ch || visited[x][y]) continue;
			visited[x][y] = true;
			dfs(x, y, ch, arr, visited);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int res = 0, res2 = 0;
		char arr[][] = new char[N][N], arr2[][] = new char[N][N];
		boolean visited[][] = new boolean[N][N], visited2[][] = new boolean[N][N];
		for(int i = 0; i < N; i++) {
			String st = sc.next();
			for(int j = 0; j < N; j++) {
				arr[i][j] = st.charAt(j);
				if(arr[i][j] =='G') arr2[i][j] = 'R';
				else arr2[i][j] = arr[i][j]; // arr2는 R과 B만으로 이루어져 있다
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(!visited[i][j]) {
					dfs(i, j, arr[i][j], arr, visited);
					res++;
				}
				if(!visited2[i][j]) {
					dfs(i, j, arr2[i][j], arr2, visited2);
					res2++;
				}
			}
		}
		System.out.println(res + " " + res2);
	}
}