BOJ[백준] - 10026 - 적록색약

Posted by ceyx
2017. 7. 14. 01:35 Algorithm 문제풀이/BOJ [백준] 문제풀이
https://www.acmicpc.net/problem/10026

 

보물섬문제와 매우 흡사합니다 ㅎㅎ 

다만, 색약 아닌 사람과 색약인 사람, 이렇게 2경우만 계산해보면 되겠네요

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
 
#define MAXNUM 100
int a[(MAXNUM * MAXNUM) + 1][4], a_blind[(MAXNUM * MAXNUM) + 1][4], q[(MAXNUM * MAXNUM) + 1], N;
char rgb[(MAXNUM * MAXNUM) + 1];
 
int BFS(int arr[][4])
{
   int head = 0, tail = 0, group = 0;
   char chk[(MAXNUM * MAXNUM) + 1= {0, };  // init visit info.
   for(int i = 1; i <= (N*N); i++)
   {
      if(!chk[i])
      {
         q[head++= i;
         while(head != tail)
         {
            int tmp = q[tail++];
            for(int j = 0; j < 4; j++)
            {
               if(arr[tmp][j] && !chk[arr[tmp][j]])
               {
                  q[head++= arr[tmp][j];
                  chk[arr[tmp][j]] = 1;
               }
            }
         }
         group++;
      }
   }
   return group;
}
int main()
{
   int i, j, tmp;
   scanf("%d"&N);
   for(i = 0; i < N; i++)
   {
      scanf("\n");
      for(j = 1; j <= N; j++)
      {
         tmp = (i*N) + j;
         scanf("%c"&rgb[tmp]);
         // [x][0] = x's east,[x][1] = x's west,[x][2] = x's south,[x][3] = x's north
         if((j - 1) % N != 0)
         {
            if(rgb[tmp - 1== rgb[tmp])
            {
               a_blind[tmp][1= a[tmp][1= tmp - 1;
               a_blind[tmp - 1][0= a[tmp - 1][0= tmp;
            }
            else if((rgb[tmp - 1== 'R' && rgb[tmp] == 'G'|| (rgb[tmp - 1== 'G' && rgb[tmp] == 'R'))
            {
               a_blind[tmp][1= tmp - 1;
               a_blind[tmp - 1][0= tmp;
            }
         }
         if(i > 0)
         {
            if(rgb[tmp - N] == rgb[tmp])
            {
               a_blind[tmp][3= a[tmp][3= tmp - N;
               a_blind[tmp - N][2= a[tmp - N][2= tmp;
            }
            else if((rgb[tmp - N] == 'R' && rgb[tmp] == 'G'|| (rgb[tmp - N] == 'G' && rgb[tmp] == 'R'))
            {
               a_blind[tmp][3= tmp - N;
               a_blind[tmp - N][2= tmp;
            }
         }
      }
   }
   printf("%d %d", BFS(a), BFS(a_blind));
   return 0;
}
cs