백준 10026번: 적록색약 (C++/코드)

 

---

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

10026번: 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 

4 3

---

DFS와 플루드 필을 알면 굉장히 쉽게 풀 수 있는 골드 난이도 문제입니다. 문제에서 말하길, 적록색약인 사람은 적색과 녹색의 차이를 느끼지 못하는 사람들을 말한다고 하네요. 그렇다면 적록색약인 사람과 아닌 사람이 보는 2가지 케이스를 모두 출력해야하기 때문에 N x N 넓이의 2차원 배열에 적록색약이 아닌 사람들이 보는 색깔들을 먼저 다 입력받고, 그 배열의 복사본을 하나 만든 뒤, 복사본 배열 안에 있는 적색과 녹색을 하나의 색깔로 통일시켜 주면 됩니다. 그 후에 각각의 배열들을 플루드 필 알고리즘을 이용해 연결 요소들의 개수를 구하면 정답입니다.

 

DFS가 혹시나 뭔지 모르시는 분이 있을까봐 간단하게만 (코딩 초보라서 저도 간단히 밖에 몰라요)  설명드리자면, 우선 그래프 탐색에 대해 알아야합니다. 그래프 탐색이란 한 점에서 시작하여 차례대로 모든 점들을 한 번씩 방문하는 것을 말합니다. DFS는 Depth First Search, 깊이 우선 탐색의 줄임말로, 백트래킹 방식을 이용한 대표적인 그래프 탐색의 일종이라고 생각하시면 됩니다.

 

밑에 첨부한 움짤을 보시면 DFS가 뭔지 쉽게 이해하실 수 있을 겁니다. 

사진 출처: https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%9D%BC:Depth-First-Search.gif

 

플루드 필 알고리즘은 DFS랑 함께 알아두시면 매우 유용한 알고리즘입니다. DFS를 통해 각 점들이 어느 점들과 연결되어있는지 알게 되었고, 이를 이용해 더 나아가 연결되어 있는 점들끼리 묶어서 하나의 그룹이라 쳤을 때, 서로 다른 그룹이 얼마나 존재하는지 찾는 방법이 바로 플루드 필 알고리즘입니다. 때문에 DFS를 알고 있다면 이를 쉽게 구현할 수 있습니다. 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int n, visit[2][105][105] = {};
char arr[2][105][105] = {};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
void dfs(int cur, int y, int x) {
  visit[cur][y][x] = 1;
  for (int i=0; i<4; i++) {
    int yy = y+dy[i];
    int xx = x+dx[i];
    if (xx < 0 or yy < 0 or xx >= n or yy >= n) {
      continue;
    }
    if (visit[cur][yy][xx] == 0 and arr[cur][y][x] == arr[cur][yy][xx]) {
      dfs(cur, yy, xx);
    }
  }
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin >> arr[0][i][j];
      arr[1][i][j]=arr[0][i][j];
      if(arr[1][i][j]=='G'){
        arr[1][i][j]='R';
      }
    }
  }
  for(int t=0; t<2; t++){
    int cnt = 0;
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        if(visit[t][i][j] == 1){
          continue;
        }
        else{
          dfs(t, i, j);
          cnt++;
        }
      }
    }
    cout << cnt << ' ';
  }
}