관리 메뉴

Mini

백준 2667 // int dfs사용법, scanf-cin혼용금지 본문

Algorithm/boj

백준 2667 // int dfs사용법, scanf-cin혼용금지

Mini_96 2023. 5. 1. 14:09

2667번: 단지번호붙이기 (acmicpc.net)

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

 

* int dfs 구현방법

1. dfs내의  int ret=1

2. main의  ret.push(dfs(i,j))

 

* scanf-cin혼용금지

ios와 cin을 지우고 scanf로 고쳤더니 정답...?

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n, c,  a[25][25], v[25][25];
int dx[] = {0,1,-1,0};
int dy[] = {1,0,0,-1};
vector<int> ret;

int dfs(int y, int x)
{
    v[y][x] = 1;
    int ret = 1;

    for (int i = 0; i < 4; ++i)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny >= n || nx >= n || ny < 0 || nx < 0) continue;

        if (a[ny][nx] == 1 && v[ny][nx] == 0)
            ret = ret + dfs(ny, nx);
    }
    return ret;

}

int main() {
    /*ios_base::sync_with_stdio(0); cin.tie(NULL);
    cin >> n;*/
    scanf("%d", &n);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            scanf("%1d", &a[i][j]);
        }
    }
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if(a[i][j]==1 && v[i][j]==0)
                ret.push_back(dfs(i, j));
        }
    }

    
    printf("%d\n", ret.size());
    sort(ret.begin(), ret.end());
    for (int a : ret) printf("%d\n",a);

   /* cout << ret.size()<<endl;
    sort(ret.begin(), ret.end());
    for (int a : ret) cout << a << endl;*/
    return 0;
}