백준 10026: 적록색약[C++]

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

 

그래프에서 구역을 찾는 문제 = DFS. 이제 바로바로 튀어나온다

적록색약인 사람과 아닌 사람의 차이는 R과 G를 똑같이 처리하냐 아니냐밖에 없으므로, 그냥 보드를 따로따로 만들고 함수도 (귀찮아서) 따로따로 만들어 각자 실행해줬다.

visited 배열도 두 개 만들어도 될 테지만 이건 그냥 memset(visited, 0, sizeof(visited)) 로 초기화해서 재사용

 

반복문으로 상하좌우를 탐색.

순환호출의 조건은 다음 좌표가 보드 안에 있을 것, 그리고 같은 색깔 즉 같은 char값을 가질 것이다. (visited가 방문되지 않았음은 당연하고)

void dfs(int x, int y){
    char color = board[x][y];
    visited[x][y] = true;
    for(int i=0;i<4;i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx>=0 && tx<n && ty>=0 && ty<n){
            char next_color = board[tx][ty];
            if(!visited[tx][ty] && color == next_color){
                dfs(tx, ty);
            }
        }
    }
}

 

메인 안에서 실행해줄 때도 마찬가지로, vistied의 false 여부를 확인해줘야 한다. 이거 까먹었다가 틀렸다

dfs가 끝났다는 것 = 해당 구역 탐색이 끝났다는 것이므로 결과값은 dfs가 종료된 다음 증가시켜준다. 이부분은 저번에 풀었던 1012번 유기농배추에서도 나왔었다.

거의 동일한 문제인데 유기농배추가 더 어려웠다... (x y 헷갈려서) 근데 솔브드 난이도는 적록색약이 더 높다. 머지?

https://day4fternoon.tistory.com/107

백준 1012: 유기농 배추 [C++]

    int ans1 = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!visited[i][j]){
                dfs(i, j);
                ans1++;
            }
        }
    }

 

적록색약의 경우에 대해서도 똑같이 해주면 정답이 나온다.

다소 길고 바보 같은 코드라는 생각도 들지만...

여튼 전체 코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

char board[101][101];
char board_weak[101][101];
bool visited[101][101];

int n;
int dx[4] = { 0, 0, -1, 1};
int dy[4] = { 1, -1, 0, 0 };

void dfs(int x, int y){
    char color = board[x][y];
    visited[x][y] = true;
    for(int i=0;i<4;i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx>=0 && tx<n && ty>=0 && ty<n){
            char next_color = board[tx][ty];
            if(!visited[tx][ty] && color == next_color){
                dfs(tx, ty);
            }
        }
    }
}

void dfs_weak(int x, int y){
    char color = board_weak[x][y];
    visited[x][y] = true;
    for(int i=0;i<4;i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx>=0 && tx<n && ty>=0 && ty<n && !visited[tx][ty]){
            char next_color = board_weak[tx][ty];
            if(color == next_color){
                dfs_weak(tx, ty);
            }
        }
    }
}

int main()
{
    cin >> n;
    char color;
    
    //입력
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> color;
            if(color=='R' || color=='B') {
                board[i][j] = color;
                board_weak[i][j] = color;
            }
            else{ //초록
                board[i][j] = color;
                board_weak[i][j] = 'R'; //적색과 똑같이
            }
        }
    }
    
    int ans1 = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!visited[i][j]){
                dfs(i, j);
                ans1++;
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    int ans2 = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!visited[i][j]){
                dfs_weak(i, j);
                ans2++;
            }
        }
    }
    
    cout << ans1 << ' ' << ans2;
    
    return 0;
}