#10026번 적록색약 (C++)

링크 : www.acmicpc.net/problem/10026

10026번: 적록색약

 

문제풀이는 다음과 같다.

 

(1) 색약이 아닌사람(ncb)과 색약인 사람(cb)를 구분한다. 

(2) 색약이 아닌 사람부터 진행한다. 그림의 첫번째 위치 [0][0]부터 시작하여, 

해당 위치를 방문한 적이 없을 경우(false) DFS를 진행한다. 

(3) 해당 위치를 방문한 적이 있음으로 표시한뒤(true), 해당 위치의 상 / 하 / 좌 / 우를 탐색한다.

(4) 상 / 하 / 좌 / 우의 값을 방문한 적이 없으며, 배열의 범위를 초과하지 않을 경우, 동시에 같은 문자값을 지닌 경우에 DFS를 진행한다. 

(5) DFS를 모두 종료하면 bool문을 초기화 해주고(memset 사용) 색약인 사람(cb)에게 DFS를 진행한다.

(6) 다른 조건은 색맹이 아닌사람(ncb)과 동일하지만, 색약인 사람은 R==G, G==B라는 조건을 두고 DFS를 진행한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n = 0, nx = 0, ny = 0,ncb = 0, cb = 0;
char arr[100][100], temp;
bool check[100][100];
int mx[4] = {1,0,-1,0};
int my[4] = {0,1,0,-1};

bool cb_track(int y, int x, char c){
   if(y<0||y>=n||x<0||x>=n||check[y][x]) return false; // 범위 초과 혹은 방문 경험이 있으면 false
   else{
       if(arr[y][x]==c) return true;
       else if(c=='R'&&arr[y][x]=='G') return true;
       else if(c=='G'&&arr[y][x]=='R') return true;
   } 
   return false;
}

void cb_dfs(int y, int x){
    check[y][x] = true;
    temp = arr[y][x];
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(cb_track(ny,nx,temp)){
            cb_dfs(ny,nx);
        }
        else continue;
    }
}

bool ncb_track(int y, int x, char c){
    if(y<0||y>=n||x<0||x>=n||check[y][x]) return false; // 범위 초과 혹은 방문 경험이 있으면 false
    else if(arr[y][x]==c) return true;
    return false;
}

void ncb_dfs(int y, int x){
    check[y][x] = true;
    temp = arr[y][x];
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(ncb_track(ny,nx,temp)){
            ncb_dfs(ny,nx);
        }
        else continue;
    }
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!check[i][j]){
                ncb_dfs(i,j);
                ncb++;
            }
        }
    }
    memset(check,false,sizeof(check));
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!check[i][j]){
                cb_dfs(i,j);
                cb++;
            }
        }
    }
    cout << ncb << " " << cb << "\n";
    return 0;
}

---

처음 채점했을때 오답이 나왔는데, 이유는 다음과 같다. 

배열의 사이즈를 100*100으로 잡고 조건문을 x>n, y>n으로 설정했었다. 

 

문자를 배열로 받을 경우 마지막에는 null문자('\n')가 삽입된다. 

때문에 배열을 딱 최대 입력값인 100*100이 아닌, 101*101의 사이즈로 설정해둬야한다. 

 

요약하자면 위의 코드도 답이지만, 

배열의 크기를 101*101로 잡고 조건문을 x>n, y>n으로 해도 정답이 나올 수 있다. 

 

(보충 설명 링크 : blog.naver.com/PostView.nhn?blogId=qbxlvnf11&logNo=221052344667&categoryNo=50&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postVie)

(C/C++)문자열 (1) 널문자 '\0'에 대한 고찰

 

 

분명 더 깔끔하고 짧게 코드를 구현해서 메모리값을 줄일 수 있는 방법이 있겠지만, 우선 스스로의 힘으로 정답을 맞추는데 집중하고싶다.