백준 10026번 적록색약 C++, BFS

리뷰

케이스를 2개로 나누어 BFS를 활용하여 푸는 문제

 

문제 풀이

1. n값과 2차 배열을 입력받은 후 2차 배열을 한개 더 생성 후 초기화 해준다. (깊은 복사 필요)
2. 0, 0부터 n-1, n-1 좌표까지 순회를 하며 만약 각 배열의 현재 좌표 값이 '_'가 아니라면 각각의 bfs를 실행해 준다.
3. bfs1은 각 색상이 주어졌을때 해당 색상이 있는 부분은 모두 '_'로 바꿔주고 case1 즉, bfs1 실행 횟수를 증가 시킨다.
4. bfs2는 위와 동일하나 만약 색상이 R 혹은 G일경우 R, G모두 '_'로 바꿔주고 case2를 증가 시킨다.
5. 2차 배열의 모든 순회와 bfs처리가 종료된 후 case1과 case2를 출력해 주면 된다.

 

참고 사항

없음

 

 

정답 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

int n, case1 = 0, case2 = 0;;
vector<string> lst1;
vector<string> lst2;

struct pos {
	int x, y;
};

void bfs1(pos xy, char c) {
	queue<pos> q;
	q.push(xy);

	while (!q.empty()) {
		pos now = q.front();
		q.pop();
		int cx = now.x, cy = now.y;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && lst1[nx][ny] == c) {
				lst1[nx][ny] = '_';
				q.push({ nx, ny});
			}
		}
	}
}

void bfs2(pos xy, char c) {
	queue<pos> q;
	q.push(xy);
	int flag = 0;
	if (c == 'R' || c == 'G') {
		flag = 1;
	}

	while (!q.empty()) {
		pos now = q.front();
		q.pop();
		int cx = now.x, cy = now.y;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (flag) {
					if (lst2[nx][ny] == 'R' || lst2[nx][ny] == 'G') {
						lst2[nx][ny] = '_';
						q.push({ nx, ny });
					}
				}
				else {
					if (lst2[nx][ny] == c) {
						lst2[nx][ny] = '_';
						q.push({ nx, ny });
					}
				}
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		lst1.push_back(s);
	}
	lst2 = lst1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (lst1[i][j] != '_') {
				bfs1({ i, j }, lst1[i][j]);
				case1++;
			}
			if (lst2[i][j] != '_') {
				bfs2({ i, j }, lst2[i][j]);
				case2++;
			}
		}
	}
	cout << case1 << " " << case2;
}