[백준] 2667번: 단지번호붙이기(DFS) - C++

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

2667번: 단지번호붙이기

---

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

int N;
int map[25][25];
bool visited[25][25];
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int num = 1;
vector<int> v;

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

void DFS(int i, int j, int &num)
{
    visited[i][j] = true;
    
    for(int d = 0; d<4;d++)
    {
        int ni = i+dir[d][0];
        int nj = j+dir[d][1];
        
        if((ni>=0 && nj>=0)&&(ni<N && nj < N))
        {
            if(!visited[ni][nj] && map[ni][nj]==1)
            {
                visited[ni][nj]=true;
                num += 1;
                DFS(ni, nj, num);
            }
        }
    }
}

int main()
{
    cin>>N;
    reset();
    for(int i=0;i<N;i++)
    {
        string s;
        cin>>s;
        for(int j = 0;j<N;j++)
            map[i][j] = s[j]-'0';
    }
    
    int sum = 0;
    for(int i=0;i<N;i++)
    {
        for(int j = 0;j<N;j++)
        {
            if(!visited[i][j] && map[i][j]==1)
            {
                num = 1;
                DFS(i, j, num);
                v.push_back(num);
                sum++;
            }
        }
    }
    sort(v.begin(), v.end());
    cout<<sum<<endl;
    for(int i = 0;i<v.size();i++)
        cout<<v[i]<<endl;
}

<입력>

한줄씩 문자열로 입력받아 각 인덱스의 문자를 - '0' 을 통해 숫자로 바꾸어 map 배열에 저장해주었다.

 

<출력>

첫번째로 출력해야할 것은 총 단지수이다. 총 단지수를 구하는 것은 유기농 배추 문제에서 출력하는 result 값과 같은 방식으로 구하면 된다.

 

생각이 필요했던 것은 오름차순으로 각 단지내 집의 수를 출력하는 것이다.

단지의 수는 가변적이기 때문에 벡터 자료형을 사용하여 저장해주었다. 

오름차순으로 정렬하는 것은 해당 문제는 정렬이 주가 아니기 때문에 sort함수를 사용했다. (그래서 시간이 오래걸린듯,,?)

 

---

 

BFS로 푼 2667번

https://lin-ing-link.tistory.com/208

[백준] 2667번: 단지번호붙이기(BFS) - C++