BOJ[백준] - 10026 - 적록색약
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 |
'Algorithm 문제풀이 > BOJ [백준] 문제풀이' 카테고리의 다른 글
BOJ[백준] - 1647 - 도시 분할 계획 (0) | 2017.07.14 |
---|---|
BOJ[백준] - 2610 - 회의준비 (0) | 2017.07.14 |
BOJ[백준] - 2589 - 보물섬 (0) | 2017.07.14 |
BOJ[백준] - 1260 - DFS와 BFS (0) | 2017.07.14 |
BOJ[백준] - 1753 - 최단경로 (0) | 2017.07.14 |