[백준/c++] 2667번: 단지번호붙이기

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

2667번: 단지번호붙이기

 

문제 요약

 

연결된 집 = 단지. 단지의 번호를 붙이자. 

1: 집이 있음 

0: 집이 없음

 

범위

 

지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)

 

 

---

 

 

시작 집을 찾기 위해 반복문을 통해 방문하지 않은 집(1)을 찾고 찾았다면 dfs를 통해 연결된 집들을 탐색(방문)한다. 연결된 집들을 모두 방문하고 만약 방문하지 않은 집이 없다면 dfs 함수가 끝난다. 다른 단지를 보러가기 위해 반복문을 통해 이동한다. 만약 다른 1이 있다면 다시 dfs 함수를 사용해서 해당 단지 내 집을 방문한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, cnt;
char map[26][26];
bool visited[26][26];
int direction[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<int> group;

void input(){
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }
}

void dfs(int x, int y){
    cnt++;
    visited[x][y] = true;
    for(int i=0; i<4; i++){
        int dx = x + direction[i][0];
        int dy = y + direction[i][1];
        if(dx < 0 || dy < 0 || dx >= n || dy >= n) continue; //지도를 벗어난 경우
        if(map[dx][dy] == '0') continue;                     //1이 아닌 경우
        if(visited[dx][dy]) continue;                        //방문한 집인 경우
        dfs(dx, dy);
    }
}

void solution(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!visited[i][j] && map[i][j] == '1'){
                cnt = 0;   //각 단지내 집 수 초기화(0)
                dfs(i, j);
                group.push_back(cnt);
            }
        }
    }
    sort(group.begin(), group.end()); //단지내 집의 수를 오름차순으로 정렬
    cout << group.size() << '\n';     //총 단지수
    for(auto it = group.begin(); it != group.end(); it++) cout << *it << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!