[BOJ] #10026 적록색약

시간 제한	메모리 제한	정답 비율
1 초	128 MB	57.637%

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

해결 방안

적록색약이 아닌 사람이 본 시선으로 나눠진 구역과, 적록색약을 가진 사람이 본 구역의 수를 출력하는 문제이다.

처음의 풀이는 함수 매개변수(x 좌표, y 좌표, color_weakness) 세 개를 받아 색약인 사람과, 그렇지 않은 사람을 구별했고, color_weakness의 값을 기반으로 조건문을 활용해서 풀었다.

그러다 다른 사람들의 풀이를 참고하여 두 번째 코드를 작성하게 되었다. 먼저 색약이 아닌사람의 시선으로 봤을 때의 구역 출력한 후에는 색약 인 사람의 시선대로 배열을 직접 수정하여 원래의 dfs 처럼 매개변수 두 개로 값을 출력할 수 있었다. 조건문도 복잡하지 않아 훨씬 보기 편하고 메모리도 감소되었다.

 

 

첫 번째 : 매개변수와 조건문 활용

메모리	시간
2100 KB	0 ms

#include<iostream>
#include<string.h>
using namespace std;
#define F(x,y,u,p) for(int x = 0; x<u; x++)for(int y = 0; y<p; y++)
int n, chk[105][105], dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 }, cnt;
char arr[105][105];
void dfs(int r, int c, int color_weakness) {
    int color = arr[r][c];
    chk[r][c] = 1;
    for (int i = 0; i < 4; i++) {
        int nr = r + dx[i], nc = c + dy[i];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n || chk[nr][nc]) continue;
        if (!color_weakness) { if (color != arr[nr][nc]) continue; }
        else if (color == 'B' && color != arr[nr][nc]) continue;
        else if ((color == 'R' || color == 'G') && arr[nr][nc] == 'B') continue;
        chk[nr][nc] = 1;
        dfs(nr, nc, color_weakness);
    }    
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
    }
    F(i, j, n, n) {
        if (!chk[i][j]) {
            dfs(i, j, 0);
            cnt++;
        }
    }
    printf("%d ", cnt);
    cnt = 0;
    memset(chk, 0, sizeof(chk));
    F(i, j, n, n) {
        if (!chk[i][j]) {
            dfs(i, j, 1);
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}

 

두 번째 : 배열 직접 수정

메모리	시간
2052 KB	0 ms

#include<iostream>
#include<string.h>
using namespace std;
#define F(x,y,u,p) for(int x = 0; x<u; x++)for(int y = 0; y<p; y++)
int n, chk[105][105], dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 }, cnt;
char arr[105][105];
void dfs(int r, int c) {
    int color = arr[r][c];
    chk[r][c] = 1;
    for (int i = 0; i < 4; i++) {
        int nr = r + dx[i], nc = c + dy[i];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n || chk[nr][nc]) continue;
        if (color != arr[nr][nc]) continue;
        chk[nr][nc] = 1;
        dfs(nr, nc);
    }    
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", arr[i]);
    }
    F(i, j, n, n) {
        if (!chk[i][j]) {
            dfs(i, j);
            cnt++;
        }
    }
    printf("%d ", cnt);
    cnt = 0;
    memset(chk, 0, sizeof(chk));
    F(i, j, n, n) {
        if (arr[i][j] == 'G') arr[i][j] = 'R';
    }
    F(i, j, n, n) {
        if (!chk[i][j]) {
            dfs(i, j);
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}