[Algorithm][DFS][정올] 2765 : 미술관람 대회

 

순서

1. 문제

2. 접근

3. 구현

문제출처 : jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2025&sca=9040

---

I. 문제

정올 USACO14.03 2765 : 미술관람 대회

미술관람 대회를 하는데 이 대회는

사회자가 빨강, 초록, 파랑으로 이루어진 NxN 픽셀의 그림을 보여주면
그 그림에 포함된 영역의 수를 빠르고 정확하게 맞추는 것이다.

예를 들어, 아래 그림은 각각 2, 1, 1개의 빨, 초, 파 영역이 있어 총 4개의 영역이 있다.

그림

한편, 적록색맹인 사람들도 있어, 빨간색과 초록색을 구별하지 못한다.
따라서, 일반 대회와 적록색맹용 대회를 따로 만드려고 한다.
사회자를 도와 영역의 수를 구하는 프로그램을 작성하여라.

요약>> 3가지 색으로 이루어진 판이 있는데, 판의 색깔 영역의 수를 구하시오.
단, 적록을 구분할 수 없는 경우도 구하시오.

 

입력형식 첫 번째 줄에는 그림의 크기 N이 주어진다. (1 ≤ N ≤ 100) 두 번째 줄 부터 N개의 줄에는 각 픽셀의 색깔이 'R'(빨강), 'G'(초록), 'B'(파랑) 중 하나로 주어진다.	출력형식 일반 꿀꿀이와 적록색맹 꿀꿀이가 보는 영역의 수를 출력. (꿀꿀이 : 참가자)
5 RRRBB GGBBB BBBRR BBRRR RRRRR	4 3

 

---

II. 접근 (DFS - FloodFill)

DFS를 이용한 FloodFill로 접근한다.

영역의 수를 구하는 법은 기본 개념 및 구현에도 올려두었으니 참고하시면 좋을 듯 합니다~
2020/12/07 - [Algorithm/DFS] - [Algorithm][DFS] DFS 개념 및 구현

우선 최대 100x100이므로 DFS로 전체 훑어도 안전하다.

1. (0,0)부터 (99,99)까지 쭉 탐색을 하면서 R일 때, G일 때, B일 경우에
해당 위치부터 DFS실행

2. 인접하고 동일한 색으로 DFS 탐색 및 확산을 진행하며 방문처리 함,
탐색이 끝나면 영역 수+1 해준다.

3. 색맹인 경우는 간단하게 R와 G를 한 가지 색으로 변경해주고 똑같은 방법 반복한다.

---

III. 구현

<hide/>
#include <stdio.h>
#include <iostream>
using namespace std;

int N;
char map1[100 + 10][100 + 10]; // 일반
char map2[100 + 10][100 + 10]; // 색맹
int norm{ 0 }; // 일반 영역수
int abnorm{ 0 }; // 색맹 영역수

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
    // 첫 번째 줄 입력받음
		cin >> map1[i];
        
		for (int j = 0; j < N; j++) {
        // 색맹의 경우로 복사함.
			map2[i][j] = map1[i][j];
			
            // G를 R로 바꾸는 작업 진행
			if (map2[i][j] == 'G') {
				map2[i][j] = 'R';
			}
		}
	}
}

// 2개의 배열을 동일하게 함수쓰려고 map도 인자로 받음.
void DFS(char(*map)[110], char color, int i, int j) {
	int dy[4] = { 0,0,-1,1 };
	int dx[4] = { 1,-1,0,0 };

	// 색이 다르면 리턴
	if (map[i][j] != color) {
		return;
	}

	//색이 같다면 들어가서 탐색
	else {
        // 0으로 방문처리
		map[i][j] = 0;
        
        // 4방향 탐색
		for (int ii = 0; ii < 4; ii++) {
			int nexty = i + dy[ii];
			int nextx = j + dx[ii];
			
            //나가면 무시
            if (nexty == -1 or nexty == N
				or nextx == -1 or nextx == N) continue;
			
            // 확산-> 한 단계 더 들어가서 return문이 있으니, 여기에는 조건 X
			DFS(map, color, nexty, nextx);
		}
	}
	return;
}

int main() {
	input();

	char C[3] = { 'R','B','G' };
	for (int c = 0; c < 3; c++) {

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {

				if (map1[i][j] == C[c]) {
					DFS(map1, C[c], i, j);
					norm++;
				}
				if (map2[i][j] == C[c]) {
					DFS(map2, C[c], i, j);
					abnorm++;
				}
			}
		}
	}

	cout << norm << " " << abnorm;

	return 0;
}

 

현재 main함수에서 charC[3]으로 3가지 경우를 반복해주며 총 3xNxN 번 탐색을 하는데(시간 낭비),

NxN만 탐색하고 방문하지 않은 경우 그 위치의 색을 인자로 넣어도 좋다.

 

* input부분에서 처리를 해주면 편한 문제들이 많다. 이 부분도 항상 유념하자!