백준 10026

1. 문제이해 
적록색약이 아닌 사람 기준)
같은 색상이 상하좌우로 인접해 있으면 같은 구역에 속한 것으로 인식

적록색약이 있는 사람 기준)
빨간색과 초록색의 차이를 느끼지 못함
빨강과 초록이 인접해 있어도 동일한 색깔로 인식

2. 문제분석
2개의 이중for문을 돌면서 RGB 구역과 R+G, B 구역을 찾음   
큐를 두개 만들어서 구역을 구분함 

시간제한은 1초로 최대 100*100 = 10,000번 연산을 수행 
2개의 이중 for문이므로 대략 20,000번 연산을 함 O(n*n) 시간복잡도로 풀어도 됨 

 

3. 코드

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

// define 뒤에 ; 써서 틀림 
// #define X first
// #define Y second

char board[101][101];
bool vis[101][101];

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

int main(void) {
	
	// 1.입력
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	
	// 2.로직
	int notColorBlind = 0;
	int colorBlind = 0;

	// 적록색약 아닌 구역 찾기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (vis[i][j] == 0) {
				queue<pair<int, int>> Q1;
				Q1.push({ i, j });
				vis[i][j] = 1;
				notColorBlind++;
				char curColor = board[i][j]; // 기준이 되는 color
				while (!Q1.empty()) {
					pair<int, int> cur = Q1.front(); Q1.pop();
					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
						if (vis[nx][ny] == 1 || curColor != board[nx][ny]) continue;
						vis[nx][ny] = 1;
						Q1.push({ nx, ny });
					}
				}
			}
		}
	}

	// vis 초기화
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			vis[i][j] = 0;
		}
	}
	
	// 적록색약 구역 찾기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (vis[i][j] == 0) {
				queue<pair<int, int>> Q1;
				Q1.push({ i, j });
				colorBlind++;
				char curColor = board[i][j]; // 기준이 되는 color
				while (!Q1.empty()) {
					pair<int, int> cur = Q1.front(); Q1.pop();
					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
						if (vis[nx][ny] == 1) continue;
						if ((curColor == 'R' || curColor == 'G') && board[nx][ny] != 'B') {
							vis[nx][ny] = 1;
							Q1.push({ nx, ny });
						}
						else if (curColor == 'B' && board[nx][ny] == 'B') {
							vis[nx][ny] = 1;
							Q1.push({ nx, ny });
						}
					}
				}
			}
		}
	}

	cout << notColorBlind << " " << colorBlind;

	return 0;
}

 

 

재풀이 코드

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

char board[101][101];
bool vis[101][101]; 
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int n;

// 구역 체크
int partSizeReturn() {
	int partSize = 0;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (vis[i][j] == 0) {
				partSize++;
				queue<pair<int, int>> Q;
				vis[i][j] = 1;
				Q.push({ i, j });
				while (!Q.empty()) {
					pair<int, int> cur = Q.front(); Q.pop();
					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
						if (board[cur.first][cur.second] != board[nx][ny] || vis[nx][ny] != 0) continue;
						vis[nx][ny] = 1;
						Q.push({ nx,ny });
					}
				}
			}
		}
	}

	return partSize;
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	// 1.입력	
	cin >> n;
	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;
		for (int j = 0; j < n; j++) {
			board[i][j] = input[j];
		}
	}
	
	// 2.로직	
	// 적록색약 X
	cout << partSizeReturn() << " ";

	// 적록색약 O	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] == 'R') {
				board[i][j] = 'G';
			}
			vis[i][j] = 0;
		}
	}
	cout << partSizeReturn();
		
	return 0;
}