baekjoon 10026:적록색약

baekjoon 10026 적록색약

10026번 적록색약

접근

연결되어 있는 것끼리 한 묶음으로 묵여야 하는데, 그 묶음의 개수를 세야겠다고 생각했다.
CLRS공부하면서 dfs가 탐색하다가 더 없으면 점프해서 다른 묶음으로 넘어갔던 생각이 나서
dfs로 풀어서 몇 번 점프 했는지 세면 되겠다고 생각했다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int dfsall(vector<vector<int>>& graph, vector<vector<bool>>& visited);
void dfs(vector<vector<int>>& graph, vector<vector<bool>>& visited, int a, int b);
int main (){

  int n; cin >> n;
  vector<vector<int>> graph(n, vector<int>(n, 0));
  vector<vector<int>> graph2(n, vector<int>(n, 0));
  vector<vector<bool>> visited(n, vector<bool>(n, false));
  vector<vector<bool>> visited2(n, vector<bool>(n, false));
  for(int i = 0; i < n; i++){
    string s; cin >> s;
    for(int j = 0; j < n; j++){
      switch(s[j])
      {
        case 'R':
          graph[i][j] = 1;
          graph2[i][j] = 1;
          break;
        case 'G':
          graph[i][j] = 2;
          graph2[i][j] = 1;
          break;
        case 'B':
          graph[i][j] = 3;
          graph2[i][j] = 2;
          break;
        default:
          break;
      }
    }
  }
  cout << dfsall(graph, visited) << " " << dfsall(graph2, visited2);
  
  
  return 0;
}
int dfsall(vector<vector<int>>& graph, vector<vector<bool>>& visited){
  int count = 0;
  for(int i = 0; i < graph.size(); i++){
    for(int j = 0; j < graph[i].size(); j++){
      if(!visited[i][j]){
        //(i, j)에서 탐색 시작해서 멈추면 count++
        dfs(graph, visited, i, j);
        count++;
      }
    }
  }
  return count;
}
void dfs(vector<vector<int>>& graph, vector<vector<bool>>& visited, int a, int b){
  visited[a][b] = true;
  //그냥 dfs와 다르게 이건 상하좌우로 탐색해야한다.
  if(a+1 < graph.size() && graph[a+1][b] == graph[a][b] && visited[a+1][b] == false){
    dfs(graph, visited, a+1, b);
  }
  if(a-1 >= 0 && graph[a-1][b] == graph[a][b] && visited[a-1][b] == false){
    dfs(graph, visited, a-1, b);
  }
  if(b+1 < graph.size() && graph[a][b+1] == graph[a][b] && visited[a][b+1] == false){
    dfs(graph, visited, a, b+1);
  }
  if(b-1 >= 0 && graph[a][b-1] == graph[a][b] && visited[a][b-1] == false){
    dfs(graph, visited, a, b-1);
  }
}

배운 점

dfs 구현 방법을 제대로 배운 것 같다.