Boj 10026 & 11724 적록색약 + 연결요소의 개수

BFS와 관련된 문제를 풀어보던 중, 적록색약이라는 문제에서 막히게 되었다.

 '격자그래프인데 어떤 방식으로 영역의 개수를 구해야 할까?'

 

'구한다면 DFS를 사용해야 할까? 아니면 BFS가 적합할까?'라는 의문에 사로잡혔다.

 격자 그래프 내에서 하나의 노드에 대해서 인접 노드에 대한 동일여부 검사를 하며 영역의 개수를 센다면 오버카운팅이 발생할 것이라는 사실은 알고 있었기 때문에 더욱 생각이 떠오르지 않았다. 하지만 문제의 예제를 노트에 그려본 직후 해답을 찾아내었다.

같은 영역은 간선으로 연결되어있다.

해당 문제는 각각의 격자점에 대해서 색 정보가 주어지면 그것이 어떤 영역의 일부인지 검사해야 했다. 이때, 상하좌우로 같은 색인 격자점이 하나라도 인접해있다면 그 두 노드는 같은 영역으로 간주된다. 

이 서술을 그대로 그림으로 옮겼더니 같은 색의 노드는 간선으로 연결되어 있고 결국 구해야 하는 것은 '연결요소의 개수'라는 것이라는 사실을 깨달았다.

 

때문에 이전에 풀었던 11724번의 풀이를 이용하여 코드를 구현해나갔다.

 

격자점을 입력 받고, 색깔이 같고, 인접한 두 노드에 대해서 연결처리를 해주었다. 그 이후 함수에 입력한 노드에 대해서 연결된 모든 노드에 대한 방문처리를 마칠 때까지 BFS를 실행하였다. 

 

하지만 이 사실을 안 이후에도 여러 문제를 직면했다. 코드를 구현하는 도중 계속해서 런타임에러가 발생하는 것이다.

수많은 시도의 흔적들

 이 때 코드를 들여다보니 문제점은 총 연결요소의 개수를 구하는 방식에 있었다. 기존의 문제 11724번을 풀이한 방식부터 잘못 되었던 것이다.

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

queue<int> q;
vector<vector<int>> arr(1001);
vector<int> visited(1001);
int cnt=0;
int N, M;

void find_connected(int V){

   visited[V]=1;

   q.push(V);

   while(!q.empty()){

      V=q.front();
       q.pop();
      for(int i=0; i<arr[V].size(); i++){
        int next=arr[V][i];
        if(!visited[next]){
            q.push(next);
            visited[next]=1;
        }

      }
   }
   cnt++;
   for(int i=1; i<=N; i++){
       if(visited[i]==0){
            find_connected(i);}
   }

}

int main(){



    cin>>N>>M;

    for(int i=0; i<M; i++){
        int u, v;
        cin>>u>>v;

        arr[u].push_back(v);
        arr[v].push_back(u);
    }

    find_connected(1);

     cout<<cnt;


}

위는 기존의 코드이다. 정답은 맞았지만 결정적인 문제점이 존재했다. 바로 BFS내부에서 다시 BFS를 호출하는 재귀함수 방식이었던 것이다. 이는 코드의 복잡도가 상승하고 cnt를 누적하는 방식에도 결정적인 문제점이 될 수 있었다. 때문에, 코드를 다음과 같이 수정하였다.

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

queue<int> q;
vector<vector<int>> arr(1001);
vector<int> visited(1001);
int cnt=0;
int N, M;

void find_connected(int V){

   visited[V]=1;

   q.push(V);

   while(!q.empty()){

      V=q.front();
       q.pop();
      for(int i=0; i<arr[V].size(); i++){
        int next=arr[V][i];
        if(!visited[next]){
            q.push(next);
            visited[next]=1;
        }

      }
   }
   


}

int main(){

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>M;

    for(int i=0; i<M; i++){
        int u, v;
        cin>>u>>v;

        arr[u].push_back(v);
        arr[v].push_back(u);
    }

    for(int i=1; i<=N; i++){
       if(visited[i]==0){
            find_connected(i);
            cnt++;
       }
   }

     cout<<cnt;


}

main함수 내에서 탐색되지 않은 공간에 대해서 BFS를 진행하여 연결요소의 개수를 구하는 것이다. 이 방식을 동일하게 10026에 적용해보았다.

#include<iostream>
#include<vector>
#include<queue>
#include<string>

using namespace std;

struct Node {
    vector<pair<int, int>> neighbors;
};//격자 그래프 내에서 연결된 요소 저장


vector<vector<Node>> connected(101, vector<Node>(101));//이차원공간, 각각의 공간에 인접노드 정보 담김
vector<vector<char>> v(101, vector<char>(101));
vector<vector<int>> visited(101, vector<int>(101));
queue<pair<int, int>> q;
int N, cnt=0;
int dx[4]={1, -1, 0, 0};
int dy[4]={0, 0, -1, 1};


void see(int X, int Y){



    q.push({X, Y});

    while(!q.empty()){
        int U=q.front().first;
        int V=q.front().second;

        for(int i=0; i<connected[U][V].neighbors.size(); i++){

            int nx=connected[U][V].neighbors[i].first;
            int ny=connected[U][V].neighbors[i].second;
            
            if(nx<1 || ny<1 || nx>N || ny>N)//인덱스 이탈 방지
            continue;
            
            if(!visited[nx][ny]){
                q.push({nx, ny});
                visited[nx][ny]=1;
            }
        }

       q.pop();
    }


}



int main(){

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);



    cin>>N;

    for(int i=1; i<=N; i++){
         string str;
         cin>>str;
         for(int j=1; j<=N; j++){
            v[i][j]=str[j-1];
         }
    }

    for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
        for(int k=0; k<4; k++){

            int nx=dx[k]+i;
            int ny=dy[k]+j;
                
            if(nx<1 || ny<1 || nx>N || ny>N)//인덱스 이탈 방지
            continue;

            if(v[nx][ny]==v[i][j]){
                connected[i][j].neighbors.push_back({nx, ny});
            }
        }
    }
}





    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(!visited[i][j]){
                see(i, j);
                cnt++;
            }
        }
    }

    cout<<cnt<<" ";

    cnt=0; //cnt초기화

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            visited[i][j]=0;
        }
    }


    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(v[i][j]=='R'){
                v[i][j]='G';
            }
        }
    }
    for (int i=1; i<=N; i++) {
    for (int j=1; j<=N; j++) {
        connected[i][j].neighbors.clear();//연결정보 초기화
    }
}

    for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
        for(int k=0; k<4; k++){
            int nx=dx[k]+i;
            int ny=dy[k]+j;
            if(nx<1 || ny<1 || nx>N || ny>N)//연결검사
            continue;

           

            if(v[nx][ny]==v[i][j]){
                connected[i][j].neighbors.push_back({nx, ny});
            }
        }
    }
}




    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(!visited[i][j]){
                see(i, j);
                cnt++;
            }
        }
    }

    cout<<cnt;


}

이 코드의 핵심은 구조체와 이를 이용한 격자점 성분에 대한 연결처리였다.  벡터를 2차원으로 선언한 후, 그 원소에는 해당 (i, j)성분과 인접한 성분 (nx, ny)를 저장하기 위해 vector<pair<int, int>>를 neighbor라는 멤버변수로 선언하였다. 이를 이용해 하나의 노드에 관해서 그 연결 노드에 접근하기 쉽도록 처리를 해주었다. 연결 노드에 대한 검사는 기존의 격작그래프 풀이법과 동일하게 4방향 탐색을 이용하였다.

 

또한 적록색약과 일반인의 시점을 다르게 하기 위해서 한번 함수를 실행한 후에는 R이 저장된 공간을 G로 바꾸어주었다. 또한 데이터 중복을 방지하기 위해서 visited, connected값을 초기화해주었다.

 

이때, Out of Bounds를 확실하게 예방하기 위해서는 연결검사를 할때 nx, ny가 인덱스를 이탈하는 것은 아닌지 확실하게 확인하도록 하자.