https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
얘도 옛날에 뭐가 잘 안풀렸었는데 잘 풀렸다.
#include <cstdio>
int n, map[110][110], visited[110][110], groups1, groups2, d[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void calc1(int x, int y, int target, int depth=0) {
if(x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || map[x][y] != target) return;
visited[x][y] = true;
for(int i = 0; i < 4; i++) {
calc1(x + d[i][0], y + d[i][1], target, depth+1);
}
if(depth == 0) groups1++;
return;
}
void calc2(int x, int y, int target, int depth=0) {
if(x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || map[x][y] != target) return;
visited[x][y] = true;
for(int i = 0; i < 4; i++) {
calc2(x + d[i][0], y + d[i][1], target, depth+1);
}
if(depth == 0) groups2++;
return;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
scanf(" %c", &map[i][j]);
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) calc1(i, j, map[i][j]);
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(map[i][j] == 'R') map[i][j] = 'G';
visited[i][j] = false;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) calc2(i, j, map[i][j]);
}
printf("%d %d\n", groups1, groups2);
}
적록색약이 아닌 사람 기준으로 한번 그룹의 수를 구하고, 모든 R을 G로 바꾼 뒤, 적록색약이 아닌 경우와 똑같이 그룹의 수를 세주면 간단하게 구할 수 있다.
포인터로 카운터를 넘기면 함수 두개 안만들어도 될텐데, 잘 몰라서 그냥 함수 두개 만들었다.
'알고리즘 > BOJ' 카테고리의 다른 글
Good Bye, BOJ 2021! (0) | 2021.12.31 |
---|---|
boj 2747, 1182, 11729 (2) | 2021.08.11 |
2252-줄 세우기 (0) | 2021.05.20 |
14502-연구소 (0) | 2021.05.19 |
17978-Washer (2) | 2020.12.25 |
15682 - 삼차 방정식 풀기 2 (0) | 2020.12.25 |
13705-Ax+Bsin(x)=C (0) | 2020.12.25 |
[Python]7420-맹독 방벽 (0) | 2020.09.25 |