[10026] 적록색약(C++)

문제

10026번: 적록색약

 

 

해결 방법

한 번에 맞은 문제가 진짜 오랜만인 것 같다 ㅋㅋ

좀 더 빨리 풀 수 있었는데 visited[i][j]가 초기화가 제대로 되지 않았던 탓에 시간을 좀 끌었다. 

 

분명히 구글링한 결과로는 이차원 배열도 ={0, };으로 초기화하면 된다고 했는데 

어찌 된 건지 나는 계속 초기화가 되지 않았다. 

 

그래서 memset이라는 함수를 사용해보았다.

memset을 사용하기 위해서는 #include <string.h> 선언을 해줘야하고

for (int i = 0 ; i < n ; i++) { 
    memset(visited[i], 0, sizeof(int)*n); 
}

위와 같은 꼴로 사용하면 된다.

 

또한 RGB와 같이 문자로 입력된 값을 어떻게 해결할까... 생각하다가

R = 0, G = 1, B = 2와 같이 숫자로 바꾸어줬다.

R	R	R	B	B
G	G	B	B	B
B	B	B	R	R
B	B	R	R	R
R	R	R	R	R

이거를

 

0	0	0	2	2
1	1	2	2	2
2	2	2	0	0
2	2	0	0	0
0	0	0	0	0

이렇게!

 

그리고 적록색맹인 사람은 빨간색과 초록색을 구분하지 못하기 때문에 1 값만 나중에 0으로 다 바꾸어주었다.

bfs 코드는 영역 구하기 문제에서 사용했던 코드와 거의 유사하지만

영역 구하기에서는 maze배열 하나로 모든 것을 해결했고,

이 문제에서는 map, visited 두 개의 배열로 문제를 풀었다는 점이 차이다.

 

 

내 코드(C++)

// [10026] 적록색약
// https://www.acmicpc.net/problem/10026
// BFS

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

int n;
char map[100][100];
int visited[100][100] = { 0, };
int cnt = 0; //the number of connected components
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
void bfs(int x, int y);
void NotColorBlind(void);
void ColorBlind(void);

int main(void)
{
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }

    NotColorBlind();
    ColorBlind();
}

void NotColorBlind(void)
{
    //not red-green blindness
    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < n; j++) {
            if (map[i][j] == 'R')
                map[i][j] = 0;
            else if (map[i][j] == 'G')
                map[i][j] = 1;
            else if (map[i][j] == 'B')
                map[i][j] = 2;
        }
    }
        
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
        	//not visited
            if (visited[i][j] == 0) 
                bfs(i, j);
        }
    }
    
    cout << cnt << " ";

    //initialization
    cnt = 0;
    
    for (int i = 0; i < n; i++) {
        memset(visited[i], 0, sizeof(int)*n);
    }
}

void ColorBlind(void)
{
    //red-green blindness
    for (int i = 0; i < n; i++) {
    	for (int j = 0; j < n; j++) {
            if (map[i][j] == 1)
                map[i][j] = 0;
        }
    }
       
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
        	//not visited
            if (visited[i][j] == 0) 
                bfs(i, j);
        }
    }
    
    cout << cnt;
}

void bfs(int x, int y)
{
    queue<pair<int, int> >q;
    q.push(make_pair(x, y));
    visited[x][y] = 1; //visited

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        //east, north, west, south
        for (int i = 0; i < 4; i++) {
            int nextx = x + dx[i];
            int nexty = y + dy[i];

            if (0 <= nextx && nextx < n && 0 <= nexty && nexty < n) {
                if (visited[nextx][nexty] == 0 && map[nextx][nexty] == map[x][y]) {
                    visited[nextx][nexty] = 1;
                    q.push(make_pair(nextx, nexty));
                }
            }
        }
    }
    
    //bfs end
    cnt++; 
}

 

main함수를 길게 쓰는 것보다 함수를 여러 개 만드는 것이 좋다고 하길래 

적록색맹이 아닐 때의 NotColorBlind() 함수와 적록색맹일 때의 ColorBlind() 두 함수로 쪼개어봤는데

어째 코드가 더 길어진 느낌은 있지만 확실히 main 함수가 짧고 간결하니까 보기 좋은 것 같다😊