백준 10026(적록색약) dfs

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

10026번: 적록색약

서로 같은 색의 인접한 것들끼리만 묶었을 때, 몇 가지로 분류할 수 있는가. 

 

이제는 딱 봐도 탐색문제이다. 

 

dfs는 재귀함수이다. 

따라서 핵심은 언제 return 할 것이고, 분류를 언제 끝냈다고 할 것인가이다. 

 

1. 벽에 부딪히면 return한다.  (index의 범위를 벗어나거나, 다른 색을 만났을 때)

2. 인접하면서 같은 색인 경우에 visited 를 true 로 해주어서 한번 조사한 곳은 중복 조사하지 않게 한다.

3. 모든 점에 대해서 dfs를 실행한다.

 

 

그리고 색약처리는 그냥 매트릭스를 두 가지 만들어서, 색약인 경우 R,G를 같은 숫자로 만들었다. 

 

for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited1[i][j]) {
				dfs1(i, j);
				cnt1++;
			}
        }
}        

위 코드는 i,j로 시작해서 인접하고 같은색인 모든 지점을 visited true로 바꾸었을 때 갯수 추가하는 코드.

 

 

 

void dfs1(int x, int y) {
	visited1[x][y] = true;
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
	for (int i = 0; i < 4; i++) {
		int c = x + dx[i];
		int d = y + dy[i];
		if (c < 0 || d < 0 || c >= N || d >= N) continue;
		if (!visited1[c][d] && mat1[x][y] == mat1[c][d]) {
			dfs1(c, d);
		}
	}
}

 

 

해당 블록에 이동했을때, 조사 완료했다고 visited true로 바꾼다. 

모든 인접한 점에 대해서 (상 하 좌 우) 조사하고 벽에 부딪히는 경우 조사하지 않고 넘긴다. 

 

#include<iostream>
using namespace std;
#define MAX 101

int N, cnt1 = 0, cnt2 = 0;
int mat1[MAX][MAX];
int mat2[MAX][MAX];
char a;
bool visited1[MAX][MAX] = { false };
bool visited2[MAX][MAX] = { false };


void dfs1(int x, int y) {
	visited1[x][y] = true;
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
	for (int i = 0; i < 4; i++) {
		int c = x + dx[i];
		int d = y + dy[i];
		if (c < 0 || d < 0 || c >= N || d >= N) continue;
		if (!visited1[c][d] && mat1[x][y] == mat1[c][d]) {
			dfs1(c, d);
		}
	}
}

void dfs2(int x, int y) {
	visited2[x][y] = true;
	int dx[4] = { 1, -1, 0, 0 };
	int dy[4] = { 0, 0, 1, -1 };
	for (int i = 0; i < 4; i++) {
		int c = x + dx[i];
		int d = y + dy[i];
		if (c < 0 || d < 0 || c >= N || d >= N) continue;
		if (!visited2[c][d] && mat2[x][y] == mat2[c][d]) {
			dfs2(c, d);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a;
			if (a == 'R') {
				mat1[i][j] = 1;
				mat2[i][j] = 1;
			}
			else if (a == 'G') {
				mat1[i][j] = 2;
				mat2[i][j] = 1;
			}
			else {
				mat1[i][j] = 3;
				mat2[i][j] = 2;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited1[i][j]) {
				dfs1(i, j);
				cnt1++;
			}
			if (!visited2[i][j]) {
				dfs2(i, j);
				cnt2++;
			}
		}
	}
	cout << cnt1 << " " << cnt2 << "\n";
}

dfs의 시간복잡도를 구하는 법에 대해서 생각을 해보았는데, 한 번 조사한 곳에 대해서는 절대 조사하지 않으니깐, 위 같은 문제의 경우 O(N^2) O(10000) 이 아닐까 생각한다.