백준 2667 - 단지번호붙이기

문제

 

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

풀이

 

DFS의 개념을 이용하면 간단하게 풀 수 있는 문제이다. 2차원 배열을 이용해서 그래프를 만든 후 2차원 배열에서 값이 1인 지점을 기준으로 DFS 탐색을 진행하면 된다. 탐색 방향은 상하좌우로 설정해주면 된다. DFS 탐색을 실행한 좌표 값은 0으로 만들어 재방문을 막는다.

 

그리고 단지의 크기를 알기 위해 sum 변수를 설정 했는데, DFS 탐색을 실행할때마다 sum 값을 증가시켜주면 한 개 단지의 크기를 알 수 있다.

 

1. 이중 for 문에서 1인 좌표에서 DFS 탐색을 실행한다

2, sum 값을 증가시키고 DFS 탐색을 실행한 좌표는 0으로 바꿔준다. (재방문을 막음)

3. 방문 좌표에서 상하좌우로 1인 좌표가 있다면 DFS 탐색을 실행한다.

4. DFS 탐색이 끝나면 sum 값을 저장하고 0으로 바꿔준다. (다음 단지의 크기를 알기 위해)

5. 이중 for 문이 끝날 때까지 1, 2, 3, 4 반복

 

 

코드

 

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
string input[25];
int N, sum;
int graph[27][27];
int result[25];
int index;
 
void dfs(int i, int j)
{
    graph[i][j] = 0;
    sum++;
 
    if (graph[i - 1][j]) dfs(i - 1, j);
    if (graph[i + 1][j]) dfs(i + 1, j);
    if (graph[i][j - 1]) dfs(i, j - 1);
    if (graph[i][j + 1]) dfs(i, j + 1);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
        
    cin >> N;
 
    for (int i = 0; i < N; i++) cin >> input[i];
    
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            graph[i][j] = input[i - 1][j - 1] - '0';
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (graph[i][j])
            {
                sum = 0;
                dfs(i, j);
                result[index++] = sum;
            }
 
    sort(result, result + index);
    
    cout << index << '\n';
    for (int i = 0; i < index; i++)
        cout << result[i] << '\n';
    
    return 0;
}