[C] 10026: 적록색약

그 동안 너무 BFS로만 풀어서 오랜만에 DFS로 풀었다

사실 구역이 몇개인지 알아보는 문제들은 그래프를 다 순회하기만 되기 때문에 BFS를 쓰든 DFS를 쓰든 아무 상관이 없다.

하지만 그래프 내에서 최소로 도달하는 순서나 그래프 순회를 넓이 우선으로 해야하는 경우는 BFS를 써야한다.

사실 아직 많이 풀어보지는 못했지만 DFS로만 풀리는 문제는 보지 못해 헷갈린다면 그냥 BFS를 써야겠다.

 

그리고 정수를 한꺼번에 배열처럼 받을때 %1d를 사용하면 하나씩 값을 얻을 수 있는데 %1c는 그런게 없다.

항상 배열의 시작이 0인지 1인지 잘생각하면서 풀어야겠다는 생각이 들었다.

또 이 문제와 같이 그래프안의 원소의 값이 달라질때는 아예 clear()함수를 만들어 초기화 시켜주는게 더 깔끔한 것 같다.

 

#include <stdio.h>

char arr[102][102];
int visit[101][101];
int n;
int x_coordinate[4]={0,0,1,-1}; //아래, 위,오른쪽, 왼쪽
int y_coordinate[4]={1,-1,0,0};

void clear()
{
  for(int j=0; j<101;j++)
    {
      for(int i=0;i<101;i++)
        {
          visit[j][i]=0;
          if(arr[j][i]=='R') //적록색약을 위한 그리드 초기화
          {
            arr[j][i]='G';
          }
        }
    }
}

void dfs(int x, int y)
{
  for(int i=0;i<4;i++)
    {
      int nx=x+x_coordinate[i];
      int ny=y+y_coordinate[i];

      if(nx>n-1||ny>n-1||nx<0||nx<0) //범위 초과
        continue;
      if(arr[ny][nx]!=arr[y][x]) //다른 색깔
        continue;

      if(visit[ny][nx]==0) //아직 안 온 곳일때
      {
        visit[ny][nx]=1;
        dfs(nx,ny);
      }          
          
    }
}

  int main(void)
  {
    scanf("%d",&n);

    // 그래프에 저장
    for(int j=0;j<n;j++)
      {
        scanf("%s",arr[j]);          
      }    
    int cnt=0;
    
    //정상 사람일때
    for(int j=0;j<n;j++)
      {
        for(int i=0;i<n;i++)
          {
            if(visit[j][i]==0)
            {
              cnt++; //구역하나 찾음
              visit[j][i]=1;
              dfs(i,j);
            }
          }
      }
    printf("%d\n",cnt);
    
    //적록색약
    clear(); //visit 초기화하고 arr 적록색약을 위해 그리드 바꿈
    cnt=0;
    for(int j=0;j<n;j++)
      {
        for(int i=0;i<n;i++)
          {
            if(visit[j][i]==0)
            {
              cnt++; //구역하나 찾음
              visit[j][i]=1;
              dfs(i,j);
            }
          }
      }
    printf("%d",cnt);   
    
  }