[BFS] 백준 10026 적록색약 C++

 

https://www.acmicpc.net/problem/10026

10026번: 적록색약

---

---

풀이 : 

 항상 느끼지만 백준 난이도는 좀 이상하다 실버 문제 못 풀때도 많은데 골드 문제라고 잔뜩 쫄아서 문제 읽어봤는데 그냥 BFS 두번 돌리면 되는거 아니야? 생각들어서 하나는 R과 G를 구분할 때 , 하나는 R과 G를 같은 색으로 취급할 때 이렇게 두개의 map을 만들어서 bfs함수를 두번돌렸더니 결과는 맞았다. 해결전략을 간단히 설명하면 주석에도 써놓았는데 R: 1, G: 2, B: 3 으로 생각했을 때 bfs로 탐색 시 현재 색깔을 저장해두고 방문하지 않은 노드 중에서 색깔이 같으면 방문하고 큐에 넣어주면 된다, RG를 구분 못할 경우에는 그냥 R과 G를 같은 숫자를 넣어주면 된다

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

int map[101][101];
int map2[101][101];
int vis[101][101];
int n;
queue<pair<int, int>> que;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
// R: 1, G: 2, B: 3
int RG = 0;
int notRG = 0;
void bfs(int a, int b) {
	int nowColor = map[a][b];
	que.push({ a,b });
	vis[a][b] = 1;

	while (!que.empty()) {
		pair<int, int> cur = que.front();
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (vis[nx][ny] == 1 || map[nx][ny] != nowColor) continue;
			vis[nx][ny] = 1;
			que.push({ nx,ny });

		}
	}
}

void bfs2(int a, int b) {
	int nowColor = map2[a][b];
	que.push({ a,b });
	vis[a][b] = 1;

	while (!que.empty()) {
		pair<int, int> cur = que.front();
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (vis[nx][ny] == 1 || map2[nx][ny] != nowColor) continue;
			vis[nx][ny] = 1;
			que.push({ nx,ny });

		}
	}
}
void initVis() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			vis[i][j] = 0;
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == 'R') {
				map[i][j] = 1;
				map2[i][j] = 1;
			}
			else if (s[j] == 'G') {
				map[i][j] = 2;
				map2[i][j] = 1;
			}
			else {
				map[i][j] = 3;
				map2[i][j] = 3;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (vis[i][j] == 0) {
				notRG++;
				bfs(i,j);
			}
		}
	}
	initVis();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (vis[i][j] == 0) {
				RG++;
				bfs2(i, j);
			}
		}
	}
	cout << notRG << " "<< RG<<endl;

}

간단하게 풀었지만 보다시피 코드가 쓸데없이 길고 중복이 많아서 나름 대로 줄여보았다! map2 사용하지 않고 vis 배열을 0으로 초기화 하면 map값을 바꿔서 그대로 bfs함수 재사용하는 방식!

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

int map[101][101];
int vis[101][101];
int n;
queue<pair<int, int>> que;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
// R: 1, G: 2, B: 3
int RG = 0;
int notRG = 0;
void bfs(int a, int b) {
	int nowColor = map[a][b];
	que.push({ a,b });
	vis[a][b] = 1;

	while (!que.empty()) {
		pair<int, int> cur = que.front();
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (vis[nx][ny] == 1 || map[nx][ny] != nowColor) continue;
			vis[nx][ny] = 1;
			que.push({ nx,ny });

		}
	}
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == 'R') {
				map[i][j] = 1;
			}
			else if (s[j] == 'G') {
				map[i][j] = 2;
			}
			else {
				map[i][j] = 3;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (vis[i][j] == 0) {
				notRG++;
				bfs(i,j);
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			vis[i][j] = 0;
			if (map[i][j] == 2) map[i][j] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (vis[i][j] == 0) {
				RG++;
				bfs(i, j);
			}
		}
	}
	cout << notRG << " "<< RG<<endl;

}