Beakjoon 10026 적록색약

11 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/10026

나의 풀이

이 문제는 DFS, BFS로 풀 수 있다.
방문하지 않은 모든 정점에서 DFS 또는 BFS를 호출하여 구역의 개수를 구할 수 있다.
DFS, BFS를 수행할 때는 인접한 4방향(상하좌우)에 대해서 같은 색을 갖는 정점을 방문하도록 한다.
적록색약이 아닌 사람은 R, G, B 각각이 다른 구역이지만 적록색약인 사람은 R과 G를 동일하게 인식하기 때문에 모든 R->G 또는 G->R로 변환해주면 된다.

풀이 코드 : 10026 적록색약

#include <string>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <iostream>

using namespace std;

vector<string> map;
int visit[100][100];

void dfs(int start_x, int start_y, int N){
    vector<pair<int, int>> stack;
    stack.push_back(make_pair(start_x, start_y));
    while(!stack.empty()){
        pair<int, int> xy = stack.back();
        int x = xy.first;
        int y = xy.second;
        stack.pop_back();
        if(visit[y][x] == 0){
            visit[y][x] = 1;
            if(x-1 >= 0 && visit[y][x-1] == 0 && map[y][x] == map[y][x-1]){
                stack.push_back(make_pair(x-1, y));
            }
            if(x+1 < N && visit[y][x+1] == 0 && map[y][x] == map[y][x+1]){
                stack.push_back(make_pair(x+1, y));
            }    
            if(y-1 >= 0 && visit[y-1][x] == 0 && map[y][x] == map[y-1][x]){
                stack.push_back(make_pair(x, y-1));
            }
            if(y+1 < N && visit[y+1][x] == 0 && map[y][x] == map[y+1][x]){
                stack.push_back(make_pair(x, y+1));
            }   
        }
    }
}

int main(){
    int N;
    string s;
    scanf("%d",&N);
    for(int i = 0;i<N;i++){
        cin>>s;
        map.push_back(s);
    }
    int count_ori = 0, count_rg = 0;
    for(int i = 0;i<N;i++){
        for(int j=0;j<N;j++){
            if(visit[i][j] == 0){
                dfs(j, i, N);
                count_ori++;
            }
        }
    }
    for(int i = 0;i<N;i++){
        memset(visit[i], 0, sizeof(int)*N);
        for(int j = 0;j<N;j++){
            if(map[i][j] == 'G') map[i][j] = 'R';
        }
    }
    for(int i = 0;i<N;i++){
        for(int j=0;j<N;j++){
            if(visit[i][j] == 0){
                dfs(j, i, N);
                count_rg++;
            }
        }
    }
    printf("%d %d", count_ori, count_rg);
}

채점결과