[백준 2667] 단지번호 붙이기

단지번호 붙이기

문제설명

첫 줄에 주어지는 입력은 지도의 크기(5<=N<=25)이다.
그리고 각 지도의 칸 마다 집이 있으면 0이고 없으면 1로 표현되어 입력된다.
입력 받은 뒤 상하좌우로 연결된 덩어리를 단지라고 하고, 각 단지 당 가구수를 구해서 오름차순으로 출력시킨다.

---

알고리즘

1. 지도의 크기와 집의 존재 여부를 입력 받는다.
2. 연결 여부와 바문 여부를 체크하여 dfs함수로 이동하여 상하좌우를 체크한다.
3. dfs함수에 접근할 때 마다 집 단지수를 측정한다.
4. dfs함수에서 빠져나와 main함수로 돌아와서 단지의 수를 증가시킨다.
5. vector에 각각 단지마다 수를 저장하고 sort 해서 출력시킨다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define MAX 50

int graph[MAX][MAX];
bool visited[MAX][MAX];
int node;
int all = 0;
int cal = 0;
void DFS(int x,int y)
{
    visited[x][y] = 1;//방문 표시
    cal++;//단지당 집 수를 세기 위함 
    if (graph[x + 1][y] == 1 && visited[x + 1][y] == 0)//현재 방문한 노드의 오른쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x + 1, y);
    if (graph[x - 1][y] == 1 && visited[x - 1][y] == 0)//현재 방문한 노드의 왼쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x - 1, y);
    if (graph[x][y + 1] == 1 && visited[x][y + 1] == 0)//현재 방문한 노드의 아래쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x, y + 1);
    if (graph[x][y - 1] == 1 && visited[x][y - 1] == 0)//현재 방문한 노드의 위쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x, y - 1);

}

int main(void)
{
    cin >> node;
    vector <int> v;
    for (int i = 0; i < node; i++)//연결 관계 입력 받기
    {
        string x;
        cin >> x;
        for (int j = 0; j < node; j++)
            graph[i][j] = x[j]-'0';
    }

    for (int i = 0; i < node; i++)
    {
        for (int j = 0; j < node; j++)
        {
            if (graph[i][j] == 1 && visited[i][j] == 0)//방문 가능한 노드로 재귀
            {
                DFS(i, j);
                all++;//전체 단지수 측정
                v.push_back(cal);
            }
            cal = 0;//단지당 집 수 초기화
        }
    }

    cout << all << endl;//전체 구역 수 출력
    sort(v.begin(), v.end());//오름 차순 정렬
    for (int i = 0; i < v.size(); i++)//단지 당 집수 출력
        cout << v[i] << endl;
    return 0;
}

---

의문점 및 막혔던 부분

먼저 입력이 이상하게 안받아져서 디버깅해보니 한번에 숫자가 들어오기 때문에 int에 넣어서 문제가 생겼다.
string 형태로 받아서 인덱스에 접근해서 graph에 넣어주었다.
또, 제대로 값이 나오는데 틀렸다고 나와서 찾아보니 배열의 크기가 충분하지 않았다.