[DFS/BFS] 단지번호붙이기 (2667)(C++)

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

2667번: 단지번호붙이기

 

1. 문제 개요

 

그림과 같이 정사각형 모양의 지도가 있을 때, 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 위, 아래, 양, 옆에 나란히 있는 칸을 이웃이라 할 때, 이웃인 단지의 수를 구하는 문제. 그림<2>에서 단지의 수는 3이 된다.

 

2. 입출력

 

 

 

3. 문제 풀이

 

DFS를 사용해서 해결할 수 있는 문제. 2차원 배열에 방문 여부를 저장하고, 이미 방문한 집은 방문하지 않도록 한다.

집을 방문할 때는 위, 아래, 양 옆을 이동해가며 연결되어 있는 그래프의 수를 탐색하며 방문 후에 집의 개수를 저장하도록 했다.

이때, 지도의 바깥 부분은 -1로 마킹해서 방문하지 않도록 했다.

또한, 집이 아닌 부분(0)도 똑같이 DFS로 탐색하여 방문을 True로 저장하되, 기록은 하지 않도록 했다.

 

 

4. 전체 코드

 

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

using namespace std;

int list[28][28];
bool visited[28][28];
int cnt = 0;
vector<int> v;

void search(int i, int j, int value) {
    if(list[i][j]!=value || visited[i][j])
        return;
    
    visited[i][j] = true;
    cnt+=1;
    search(i-1,j,value);
    search(i,j-1,value);
    search(i+1,j,value);
    search(i,j+1,value);
    return;
}

int main(void) {
    int N;
    cin >> N;
    
    for(int i=1;i<=N;i++) {
        string temp;
        cin >> temp;
        for(int j=1;j<=N;j++)
            list[i][j] = temp[j-1]-'0';
    }
    
    for(int i=0;i<=N+1;i++) {
        list[N+1][i] = -1;
        list[i][N+1] = -1;
        list[0][i] = -1;
        list[i][0] = -1;
    }
    
    
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            if(!visited[i][j]&&list[i][j]==1){
                cnt = 0;
                search(i, j, 1);
                v.push_back(cnt);
            } else if(!visited[i][j]&&list[i][j]==0) {
                search(i, j, 0);
            }
        }
    }
    
    sort(v.begin(), v.end());
    
    cout << v.size() << "\n";
    for(int i=0;i<v.size();i++) cout << v[i] << "\n";
    
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!