백준 10026 적록색약

https://www.acmicpc.net/status?user_id=totw2018&problem_id=10026&from_mine=1 

채점 현황

 

- 그래프 탐색 알고리즘 문제이다. 시간복잡도는 그래프 탐색 + 문자 치환 탐색 + 그래프 탐색 해서 총 O(n^2)이다.

 

- 특이하게, 입력을 문자열들로 준다. 따라서 필자는 string 자료형으로 총 n번을 입력받고, 입력 받을 때 마다 문자 하나하나를 char 배열 map에 저장을 했다. 또한, 처음 주어진 map에서 BFS 한 번, 이 후 맵의 G를 모두 R 문자로 바꿔준 다음 또 한 번 BFS를 진행하였다. 이러한 점 외에는 다른 그래프 탐색 문제와 크게 다를 것이 없다.

 

- 여담으로, 15분만에 문제를 풀어내서 뿌듯하다. 나도 이제 중수 쯤 됬을까

 

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
using namespace std;
char map[101][101];
bool visited[101][101];
int n, answer;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
void bfs(int s_x, int s_y) {
	answer++;
	queue<pair<int, int>> q;
	visited[s_x][s_y] = true;
	q.push({ s_x, s_y });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (visited[nx][ny]) continue;
			if (map[x][y] != map[nx][ny]) continue;
			visited[nx][ny] = true;
			q.push({ nx,ny });
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < n; j++) {
			map[i][j] = temp[j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) bfs(i, j);
		}
	}
	cout << answer << ' '; answer = 0;
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 'G') map[i][j] = 'R';
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j]) bfs(i, j);
		}
	}
	cout << answer;
	return 0;
}