백준 2667 - 단지번호 붙이기 (그래프 탐색, 순회)

1. 배경지식

BFS 와 DFS 

 - DFS는 깊이 우선 탐색으로 끝까지 간다음 끝에 다다르면 첫 분기점으로 다시 돌아오는 재귀적인 수행을 하는 친구이고, 

 - BFS는 넓이 우선 탐색으로 한 노드에 들어가서 연결된 노드들을 모두 탐색하고 다음 노드로 넘어가는 식의 친구이다. 

 

구현적인 측면에서

DFS는 한 노드에 대해서 연결된 노드들을 재귀적으로 방문하여 첫 시작 노드로부터, 재귀가 종료될 때까지 자동으로 함수가 실행되고 종료되는 수행을 하고, 

BFS는 한 노드에 대해서 연결된 노드들을 모두 큐에 넣은 다음, 큐가 빌 때까지 다시 큐에서 한 노드를 꺼내 같은 수행을 반복하는 수행을 한다. 

 

쓰임의 측면에서  (앞으로 내용이 더 추가될 부분.)

DFS는 분기되는 응용에서 사용되고, 

BFS는 연결된 한 단지를 방문하는 경우, 한 지점에서 특정 지점까지 이동하는 최단경로 등의 응용에서 사용된다. 

 

 

그래프의 구현 측면에서 

인접리스트로 구현 시에는 

각 노드 별로 연결된 노드들이 연결리스트로 구현되어 있고 

인접행렬로 구현시에는

각 노드들이 2차원 배열의 인덱스가 되어 간선 사이의 가중치가 배열 값이 된다.

(단, 가중치를 전부 1로 표현하여 연결여부만을 나타낼 수도 있다.)

 

 

이런 그림의 형식과 같다. 

무방향그래프일 때는 서로 중복된 인접리스트가 구현되고, 인접행렬에서도 대칭으로 나타나는 반면,

방향그래프일 때는 한쪽에만 노드가 연결되어 어디에서 어디로 연결된 건지 명확하게 나타낼 수 있고,

인접행렬도 행과 열이 각각 from 과 to를 의미하여 비대칭적으로 나타나서 구현될 수 있다. 

 

 

그래프를 DFS, BFS로 순회할 수 있는 반면 2차원 배열도 그래프로 취급하여, 상하좌우로 이동하면서 그래프 탐색으로 구현할 수 있다. 

단, 인덱스 접근 범위를 제한하여 잘못 가는 경우가 없도록 해야 한다. 

그 예시가 바로 2667번: 단지번호 붙이기이다. 

 

 

 

--------------------------------------------------------------------------------------------------

 

2. 문제

 

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

----------------------------------------------------------------------------------------------------------------------

 

3. 구현

C++로 구현해서 좀 더 쉽게 그래프를 구현하도록 하였다. 

 

 

 1.1. 입력

int main()
{
    unsigned long long  num;
    scanf("%d", &N);
    init();
    for(int i=1;i<=N;i++) {
        scanf("%lld", &num);
        for (int j = N; j>=1; j--)
        {
            map[i][j] = num%10;
            num/=10;
    	}
    }
  }

다음과 같은 입력 구조를 만들었다.

N<=25임을 감안할 때 한 칸에는 25자리 정수까지 들어올 수 있고, unsigned long long 형 정수는 8byte 까지 처리할 수 있다. 

이 때 2^32 * 2 = 8589934592  대충 이정도의 숫자까지 받아들일 수 있으므로, 이 방식이 잘못되었다는 걸 알았다. 

 

 

 

 

input 함수를 만들어서, 문자열로 입력받은 다음 처리하도록 하였다. 

 

void input(int i, char *s) {
    for(int j=1;j<=N;j++)
        map[i][j] = *s++ - '0';
}

int main()
{
    char string[26];
    scanf("%d", &N);
    init();
    for(int i=1;i<=N;i++) {
        scanf("%s", string);
        input(i,string);
    }
...
}

 

 

2. BFS를 구현하되, 매 시작지점에서 저장할 visit의 값을 1증가시킴으로써 visit이 단지번호를 부여하는 역할까지 수행하게끔 만들었다. 

visit(확인용코드)을 출력하면 다음과 같다. 

 

출력을 위해서는 여기서 1의 수, 2의 수.... 등을 모두 세서 출력할수도 있으나,

BFS를 수행할 때마다 따로 village 배열에 각 단지별로 그 세대수를 저장하도록 코드를  짰다.

 

villages 즉 단지의 최대 수는 25*25 = 6250 이므로, 6300의 공간의 int형 배열을 설정하였다. 

 

 

전체 구현 코드는 다음과 같다. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

#define TRUE 1
#define FALSE 0

using namespace std;

queue<pair <pair<int, int>, int> > Q;
int map[26][26];
int visited[26][26];
int visit=1;
int village[6300], idx = 0;

int N;

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

void BFS()
{
    int cnt = 0;
    while(!Q.empty())
    {
        int r = Q.front().first.first;
        int c = Q.front().first.second;
        Q.pop();
        if(visited[r][c] != FALSE)
            continue;
        cnt++;
        visited[r][c] = visit;
        if (r+1 <=N && map[r+1][c] == 1)
            Q.push(make_pair(make_pair(r+1,c),map[r+1][c]));
        if (c+1 <=N  && map[r][c+1] == 1)
            Q.push(make_pair(make_pair(r,c+1),map[r][c+1]));
        if (r-1 >=0  && map[r-1][c] == 1)
            Q.push(make_pair(make_pair(r-1,c),map[r-1][c]));
        if (c-1 >=0 && map[r][c-1] == 1)
            Q.push(make_pair(make_pair(r,c-1),map[r][c-1]));
    }
    village[idx++]= cnt;
}

void input(int i, char *s) {
    for(int j=1;j<=N;j++)
        map[i][j] = *s++ - '0';
}

int main()
{
    char string[26];
    scanf("%d", &N);
    init();
    for(int i=1;i<=N;i++) {
        scanf("%s", string);
        input(i,string);
    }

    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(visited[i][j] == FALSE && map[i][j] == 1) {
                Q.push(make_pair(make_pair(i, j), map[i][j]));
                BFS();
                visit++;
            }
        }
    }
//    printf("확인용\n");
//    for(int i=1;i<=N;i++)
//    {
//        for(int j=1;j<=N;j++)
//        {
//            printf("%d ", visited[i][j]);
//        }
//        printf("\n");
//    }
    printf("%d\n", visit-1);
    for(int i=0;i<idx;i++)
    {
        for(int j=0;j<idx-i-1;j++)
        {
            if(village[j] > village[j+1])
            {
                int temp = village[j];
                village[j] = village[j+1];
                village[j+1] = temp;
            }
        }
    }
    for(int i=0;i<idx;i++)
        printf("%d\n", village[i]);
}