백준 | 10026. 적녹색약

 

 

1. idea

• string 함수 만들어서 string 입력받기
• 방문처리는 v로 변경처리
• 배열 돌면서 v 가 아니고, 시작점의 char이랑 같으면 dfs 계속 돌기
• ans vector 에 시작점에 나온 글자 넣기
• 색맹이 아닌 사람이 보는 구역은 ans vector의 size
• 색맹인 사람이 보는 구역은 ans 순회하면서 G랑 R 붙어있는 부분을 --하기

(이게 오류가 나서 다시 idea를 수정한게)

• 색맹용 vector를 새로 만들어서 맨 처음에 string으로 입력을 받고, 색맹이 아닌 사람은 B=1, R=2, G=3 // 색맹인 사람은 B=1, 나머지는 2로 vector에 입력하기
• 색맹용 cnt랑 비색맹용 cnt 만들고
• for문 돌면서 시작점이랑 똑같은 구역 dfs하되, 색맹지도, 아닌지도 각각 알아서 돌고, 그 구간 끝나서 나오면 각각의 cnt를 ++하는거!! 그러면 dfs도 새로 안만들어도 되고, for문도 안만들어도 된다

 

2 DFS 함수 만들기

void dfs(vector<string>&picture, int x, int y, int end, char comp){
    int dx[] = {0, 0, -1, 1};
    int dy[] = {1, -1, 0, 0};

    picture[y][x] = 'v';
    
    for(int i =0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx >= 0 && nx < end && ny >= 0 && ny < end){
            if(picture[ny][nx]==comp) dfs(picture, nx, ny, end, comp);
        }
    }
}

 

3. 전체 지도 순회

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(picture[i][j] != 'v'){
                ans.push_back(picture[i][j]);
                dfs(picture, j, i, N, picture[i][j]);
            }
        }
    }

 

4. 색맹인 사람이 보는 구역

    int blind_cnt = ans.size();
    for(int i = 1; i < ans.size(); ++i){
        if(ans[i] == 'R' || ans[i] == 'G'){
            if(ans[i-1] == 'R' || ans[i-1] == 'G') blind_cnt--;
        }
    }

 

5. 오류 발생!!!!!!!!!!!!!!

예외 코드

5
RGBRG
GRBGR
BGRBG
RGBRG
GRBGR

(21 6) 나와야하는데 (21 9) 나옴. 덩어리 설정을 제대로 못해서 그런듯

6. 오류 수정

아예 색맹용 지도를 따로 만들어서 dfs 만들어논거를 같이 돌게하면 되지 않을까?

그러면 for문도 여러개 안돌아도 괜찮고....

 

7. 수정된 코드 (DFS는 인풋이랑 방문처리만 조금 수정)

    vector<vector<int>>picture(N, vector<int>(N));
    vector<vector<int>>b_p(N, vector<int>(N));

    for(int i = 0; i<N; ++i){
        cin >> line;
        for(int j = 0; j < N; ++j){
            picture[i][j] = line[j]=='B'? 1 : line[j]=='R'? 2 : 3;
            b_p[i][j] = line[j]=='B'? 1 : 2;
        }
    }

    int non_blind =0, blind =0;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(picture[i][j]!= 0){
                dfs(picture, j, i, N, picture[i][j]);
                non_blind++;
            }

            if(b_p[i][j]!= 0){
                dfs(b_p, j, i, N, b_p[i][j]);
                blind++;
            }
        }
    }

 

 

8.코드 전문

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>&p, int x, int y, int end, char comp){
    int dx[] = {0, 0, -1, 1};
    int dy[] = {1, -1, 0, 0};

    p[y][x] = 0;
    
    for(int i =0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx >= 0 && nx < end && ny >= 0 && ny < end){
            if(p[ny][nx]==comp) dfs(p, nx, ny, end, comp);
        }
    }
}

int main(){
    int N;
    string line;
    cin >> N;
    
    vector<vector<int>>picture(N, vector<int>(N));
    vector<vector<int>>b_p(N, vector<int>(N));

    for(int i = 0; i<N; ++i){
        cin >> line;
        for(int j = 0; j < N; ++j){
            picture[i][j] = line[j]=='B'? 1 : line[j]=='R'? 2 : 3;
            b_p[i][j] = line[j]=='B'? 1 : 2;
        }
    }

    int non_blind =0, blind =0;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(picture[i][j]!= 0){
                dfs(picture, j, i, N, picture[i][j]);
                non_blind++;
            }

            if(b_p[i][j]!= 0){
                dfs(b_p, j, i, N, b_p[i][j]);
                blind++;
            }
        }
    }

    cout << non_blind << " " << blind;
    
    return 0;
}

해냈다!!! 조금 뿌듯할지도

내일은 BFS를 공부해봐야겠다.