[DFS, 난이도 중하] 백준 10026번 적록색약 (BFS, DFS 모두 사용)

 

제출번호 21761134가 DFS로,

제출번호 21760828이 BFS로 해결해서 정답처리된 소스코드이다. 

 

맵의 모든 구역을 탐색하면서 탐색하지 않은 좌표에서 BFS/DFS를 호출하여 , 인접 색들을 만나면 전부 방문처리를 한다.

BFS/DFS를 호출할 때마다 group 카운트를 늘려나가서 몇 개의 그룹으로 이루어져 있는지 계산하면 된다.

 

적록색약이 아닌사람에 대해서 map배열, visited배열, group변수를,

적록색약인 사람에 대해서 map2배열, visited2배열, group2변수를 썼다.

두 가지 경우에 대해 모두 수행해주었다.

 

적록색약인 사람인 경우 모든 초록색을 빨강색으로 인지하는 것으로 가정했다.

즉 map2에서는 R 혹은 B만 존재한다. 애초에 모든 G를 R로 바꾼 것이다.

 

이렇게 접근하면 문제가 해결 된다. 어려운 편인 문제는 아니다.

<BFS>

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
char map[101][101];
char map2[101][101];
bool visited[101][101];
bool visited2[101][101];
vector<int> house;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	queue<pair<int, int> > q;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			map[i][j] = s[j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 'G') map2[i][j] = 'R';
			else map2[i][j]=map[i][j];
		}
	}
	int group = 0;
	int group2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				visited[i][j] = true;
				q.push(make_pair(i, j));
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					for (int k = 0; k < 4; k++) {
						if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= n) continue;
						if (map[x][y]==map[x + dx[k]][y + dy[k]] && !visited[x + dx[k]][y + dy[k]]) {
							q.push(make_pair(x + dx[k], y + dy[k]));
							visited[x + dx[k]][y + dy[k]] = true;
						}
					}
				}
				group++;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited2[i][j]) {
				visited2[i][j] = true;
				q.push(make_pair(i, j));
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					for (int k = 0; k < 4; k++) {
						if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= n) continue;
						if (map2[x][y] == map2[x + dx[k]][y + dy[k]] && !visited2[x + dx[k]][y + dy[k]]) {
							q.push(make_pair(x + dx[k], y + dy[k]));
							visited2[x + dx[k]][y + dy[k]] = true;
						}
					}
				}
				group2++;
			}
		}
	}
	cout << group << " " << group2;
}

 

<DFS>

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
char map[101][101];
char map2[101][101];
bool visited[101][101];
bool visited2[101][101];
vector<int> house;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n;
void dfs(int x,int y) {
	visited[x][y] = true;
	for (int k = 0; k < 4; k++) {
		if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= n) continue;
		if (map[x][y] == map[x + dx[k]][y + dy[k]] && !visited[x + dx[k]][y + dy[k]]) {
			visited[x + dx[k]][y + dy[k]] = true;
			dfs(x + dx[k], y + dy[k]);
		}
	}
}
void dfs2(int x, int y) {
	visited2[x][y] = true;
	for (int k = 0; k < 4; k++) {
		if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= n) continue;
		if (map2[x][y] == map2[x + dx[k]][y + dy[k]] && !visited2[x + dx[k]][y + dy[k]]) {
			visited2[x + dx[k]][y + dy[k]] = true;
			dfs2(x + dx[k], y + dy[k]);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	queue<pair<int, int> > q;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			map[i][j] = s[j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 'G') map2[i][j] = 'R';
			else map2[i][j]=map[i][j];
		}
	}
	int group = 0;
	int group2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) {
				dfs(i, j);
				group++;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited2[i][j]) {
				dfs2(i, j);
				group2++;
			}
		}
	}
	cout << group << " " << group2;
}

 

 

 

2021-09-19 추가 - 숏코딩 상위 6%

문제를 1년 뒤에 다시 풀어보는 도중, 위의 방식에 비해 코드를 더 줄일 수 있을 것 같아서 도전해보았다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
queue<pair<int,int> > q;
char map[101][101];
bool visited[101][101];
int x[4] = {1,-1,0,0};
int y[4] = {0,0,1,-1};
int ans[2],n,a,b;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		for(int j=0;j<n;j++)map[i][j]=s[j];
	}
	for(int t=0;t<2;t++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(visited[i][j]) continue;
				ans[t]++;
				char c=map[i][j];
				q.push(make_pair(i, j));
				while(!q.empty()){
					int fx=q.front().first;
					int fy=q.front().second;
					visited[fx][fy]=true;
					q.pop();
					for(int k=0;k<4;k++){
						a=fx+x[k];b=fy+y[k];
						if(a<0||a>=n||b<0||b>=n) continue;
						if(visited[a][b]) continue;
						if((t==1&&(c!='B'&&map[a][b]!='B'))||map[a][b]==c){
							visited[a][b]=true;
							q.push(make_pair(a,b));
						}
					}
				}
			}
		}
		memset(visited, false, sizeof(visited));
	}
	cout << ans[0] << " " << ans[1];
}