[백준 알고리즘] 2667번 단지번호붙이기(BFS)

이번에는 BFS, DFS를 활용할 수 있는 문제를 풀어봅시다. 먼저 간단하게 탐색만 진행할 수 있는 문제를 준비해보았습니다.

2667번 단지번호붙이기 이 문제입니다!!!

문제는 다음과 같습니다.

저는 BFS로 접근해보았습니다. 풀이 방식은 매우 간단하게 BFS의 이론적인 내용을 그~대로 사용하였습니다. BFS의 활용이라고 보면 되겠네요!!!

먼저 main 코드부터 살펴보겠습니다!!

#include <iostream>
#include <cstdio>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

int N;
int map[25][25];
int multiplex[700] = {0,};
int amountOfMultiplex;

int main()
{
    cin>>N;
    amountOfMultiplex = 3;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            scanf("%1d",&map[i][j]);
        }
    }
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(map[i][j] == 1) BFS(i,j,amountOfMultiplex++);
        }
    }
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(map[i][j] >=3) multiplex[map[i][j]-3]+=1;
        }
    }
    amountOfMultiplex-=3;
    sort(multiplex,multiplex+amountOfMultiplex);
    cout<<amountOfMultiplex<<endl;
    for(int i=0; i<amountOfMultiplex; i++) cout<<multiplex[i]<<endl;
    return 0;
}

먼저 main에서 새로 알게된 TIP... 

scanf("%1d",&map[i][j]); 

이렇게 숫자를 받으면 101010으로 입력해도 숫자 하나씩 저장 되더라구요..! 몰랐는데 신기하네요.. 

c++ 사용하시는 분들도 cstdio라이브러리를 include하면 scanf쓸 수 있으니까 이런 경우 용이하겠네요ㅎㅎ 

자 중요한 부분은 두 번째 이중 for loop겠네요. 입력받은 배열에서 1의 성분을 보면 BFS를 시작하는 거를 알 수 있네요. 이게 default값이 0, 1이다 보니까 단지 개수를 의미하는 amountOfMultiplex를 3부터 시작했으니까 유의해주시기 바랍니다. 그 다음엔 문제에서 원하는 output에 맞춰서 단지 갯수를 정렬해주고, 출력해주는 것... 쉽네요!! 

다음은 BFS함수입니다.

void BFS(int i, int j, int multiplex)
{
    queue<pair<int,int>> q;
    q.push(pair<int,int>(i,j));
    map[i][j] = multiplex;
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        //right
        if((y+1<N) && map[x][y+1]==1)
        {
            map[x][y+1] = multiplex;
            q.push(pair<int,int>(x,y+1));
        }
        //left
        if((y-1<N) && map[x][y-1]==1)
        {
            map[x][y-1] = multiplex;
            q.push(pair<int,int>(x,y-1));
        }
        //up
        if((x+1<N) && map[x+1][y]==1)
        {
            map[x+1][y] = multiplex;
            q.push(pair<int,int>(x+1,y));
        }
        //down
        if((x-1<N) && map[x-1][y]==1)
        {
            map[x-1][y] = multiplex;
            q.push(pair<int,int>(x-1,y));
        }
    }
}

이 부분도 BFS가 어렵지 않은 알고리즘이기 때문에 이해가 금방 되리라 믿습니다. 이때 조금 시간을 사용했던 부분은 pair를 사용하는 부분인데, 2차원 좌표를 사용하기 때문에 이것을 어떻게 저장할까 고민을 했었거든용. 이리저리 찾아보니까 pair라는 용이한 자료형이 있네요ㅎㅎㅎㅎ pair는 utility라이브러리를 include하면 사용할 수 있습니다!!!! 알고리즘을 보면 좌표 기준 4방향(오른쪽, 왼쪽, 위, 아래)를 비교해서 1이면 인접 노드의 multiplex번호를 할당해주는 것을 알 수 있습니다. 코드를 짧게 하고싶으신 분은 recursive로 나타낼 수도 있어요.

map[x-1][y] = multiplex;
q.push(pair<int,int>(x-1,y));

이 두줄을
bfs(x-1,y,multiplex);

이렇게 해주면 간단하겠네요!! 재귀는 함수 호출 overhead가 있기 때문에 연산량이 많아지면 느려질 수도 있겠네요ㅎㅎ  

최종 코드는 아래 url로 가시면 됩니당.

  GitHub - dinoHee/baekjoon-2667 

이렇게 간단하게 마무리하였습니다!!! 

처음에 이 방법으로 문제를 접근하는게 맞는 것인지 고민을 했었는데, 시간 복잡도를 생각해서 그런건지.. 자신이 없는건지..ㅎㅎ 이젠 과감하게 처음 생각한 것으로 도전을 해보렵니다. 

 감사합니다!!!!