[백준] DFS/BFS 2667번: 단지번호붙이기

C.K. ·2022년 6월 24일
0

baekjoon

목록 보기
32/67

문제

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

입력

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

출력

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

Approach

사용 알고리즘: dfs

  • 지도의 정보를 2차원 matrix로 입력받는다
  • 특정한 지점의 값이 1이면서 아직 방문하지 않은 지점이라면 방문처리 후 상, 하, 좌, 우 지점들도 확인 후 같은 조건이라면 방문 처리
  • 또 해당 지점에서 상, 하, 좌, 우 지점들을 확인한 후 조건에 맞으면 방문 처리
  • 위 과정들을 반복하면서 결괏값 갱신 (모든 노드 방문)
  • 이때 한 단지를 방문할 때 마다 그 단지내 집의 수를 저장해놓고 나중에 벡터에 넣는다
  • 벡터를 오름차순으로 정렬해서 출력한다

Source Code

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

int n; 
int graph[26][26]; // 지도를 저장할 2차원 matrix

bool dfs(int x, int y, int& count)
{
	// 지도 밖을 벗어나면 즉시 종료 
    if (x <= -1 || y <= -1 || x >= n || y >= n)
        return false;
    if (graph[x][y] == 1) // 집이 있는 지점이면 
    {
        graph[x][y] = 0; // 방문 처리 
        count++; // 집의 갯수 업데이트
        
        // 상,하,좌,우 똑같이 탐색
        dfs(x + 1, y, count);
        dfs(x - 1, y, count);
        dfs(x, y + 1, count);
        dfs(x, y - 1, count);
        return true;
    }
    return false;
}

int main() {
    
    cin >> n;
    
    // 지도 정보 입력받기 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%1d", &graph[i][j]);
        }
    }
    
    int result = 0; // 단지 갯수 
    vector<int> cnt; // 각 단지내 집의 수들을 담을 벡터 
    int count = 0; // 집의 갯수 
    
    // 모든 노드를 확인하면서 dfs수행 
    for (int k = 0; k < n; k++)
    {
        for (int m = 0; m < n; m++)
        {
            if (dfs(k, m, count))
            {
                result++;
                cnt.push_back(count);
                count = 0; // 집의 갯수 초기화 (한 단지 탐색 끝나면)
            }
        }
    }
    
    cout << result << '\n'; // 단지 갯수 출력
    
    sort(cnt.begin(), cnt.end()); // 오름차순 정렬 
    for (int l = 0; l < cnt.size(); l++)
        cout << cnt[l] << '\n'; // 각 단지내 집의 갯수 오름차순 출력

    return 0;
}
profile
1일 1알고리즘

0개의 댓글