[ BFS | 기본문제] 10026번 : 적록색약

 

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

---

 걸린 시간 

1시간

 

 생각

- 기본 BFS에서 적록색약의 경우, 같은 구역을 구분하는 조건만 달리 구현하면 된다고 생각.

---

 구현 코드 

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

int n;
string board[101];
bool visit[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;

void bfs()
{
	while (!q.empty()) {
		auto 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 >= n || ny >= n || nx < 0 || ny < 0) continue;
			if (visit[nx][ny] != 0 || board[cur.first][cur.second] != board[nx][ny]) continue;
			q.push({ nx,ny });
			q.push({ nx,ny });
			visit[nx][ny] = true;
		}
	}
}

void red_green_bfs()
{
	while (!q.empty()) {
		auto 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 >= n || ny >= n || nx < 0 || ny < 0) continue;
			if (visit[nx][ny] != 0) continue;
			if (board[cur.first][cur.second] != 'B') {	//적녹색 구역일 경우
				if (board[nx][ny] == 'B') continue;	//파란색이면 out
			}
			else if (board[cur.first][cur.second] != board[nx][ny])	continue;
			q.push({ nx,ny });
			visit[nx][ny] = true;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}
	int testCase = 2;
	while (testCase != 0)
	{
		int area = 0;
		for (int i = 0; i < n; i++) {
			fill(visit[i], visit[i] + n, false);
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visit[i][j] == 0) {
					q.push({ i,j });
					visit[i][j] = true;
					area++;
				}
				if (testCase == 2)
					bfs();
				else
					red_green_bfs();
			}
		}
		cout << area << " ";
		testCase--;
	}
}

 

 리뷰 

적록색약인 사람의 BFS 함수를 따로 구현하면서 조건문 하나빼고는 다같은 내용이라 더 효율적인 방법이 있을 거 같았는데 적록색약 BFS를 돌기 전에 board 자체를 R은 G로 하는 식으로 바꾸는 방법이 있었다...!