백준 2667. 단지 번호 붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

다시 푼 문제, 이전 글 : tose33.tistory.com/26

 

동서남북 이동은 다음과 같이 처리

int dx[4] = {0, 1, 0, -1}; // n,e,s,w
int dy[4] = {-1, 0, 1, 0};

 

입력이 띄어쓰기 없이 쭉 주어져서 다음과 같이 처리

for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            scanf("%1d", &apt[i][j]);
        }
    }

 

 

지금까지 푼 dfs, bfs 문제와 같지만 지금까지는 연결관계가 간선의 정보로 주어졌다면

이 문제는 배열에 주어짐. 따라서 직접 동서남북으로 이동해서 0인지 1인지 판단해야함.

 

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

int N;
int aptnum = 0;
int group = 1;
int apt[26][26]; // 아파트 원본
int res[26][26]; // 그룹번호 찍힐 배열
int dx[4] = {0, 1, 0, -1}; // n,e,s,w
int dy[4] = {-1, 0, 1, 0};
vector<int> v;

void dfs(int x, int y) {
    if(res[x][y] > 0 || apt[x][y] != 1) return;
    res[x][y] = group;
    aptnum++;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i]; // n,e,s,w 이동
        int ny = y + dy[i];
        if(nx < 0 || nx > N || ny < 0 || ny > N) continue;
        dfs(nx,ny);
    }
}



int main() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            scanf("%1d", &apt[i][j]);
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(apt[i][j] == 1 && res[i][j] == 0) { // 아파트가 있고, 방문하지 않은
                dfs(i,j);
                group++;

                v.push_back(aptnum);
                aptnum = 0;
            }
        }
    }

    cout << group - 1 << endl;
    sort(v.begin(), v.end());
    for(int x : v) cout << x << endl;

}