[백준 알고리즘] 2667번 문제 단지번호 붙이기

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

 

알고리즘 : DFS

언어: C++

 

visit와 재귀함수를 통해 구현

전형적인 DFS 문제

알고리즘을 이해하고 구현하는데에 집중하여 코드를 작성했다. 효율성이라던가 기타 등등은 크게 고려하지 않음

논리적인 이해만 있으면 풀기 가능

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int n;
vector<vector<char>> arr;
vector<vector<int>> visit;
int cnt;
void dfs(int x, int y) {
    visit[x][y] = 1;
    cnt ++;

    for (int i = 0; i < 4; i ++) {
        int xpoint = x + dx[i];
        int ypoint = y + dy[i];
        
        if (xpoint < 0 || ypoint < 0 || xpoint >= n || ypoint >= n)
            continue;

        if (!visit[xpoint][ypoint] && arr[xpoint][ypoint] == '1') {
            dfs(xpoint,ypoint);
        }
    }
}

int main() {

    vector<int> answer;
    // 입력 셋팅
    cin >> n;
    arr.resize(n, vector<char>(n));
    visit.resize(n, vector<int>(n,0));
    for(int i = 0 ; i < n; i ++) {
        for(int j = 0 ; j < n; j++){
            cin >> arr[i][j];
        }
    }

    // 방문
    for (int i = 0 ; i < n ; i++){
        for (int j = 0; j < n ; j++){
           if (arr[i][j] == '1' && !visit[i][j]) {
            cnt = 0;
            dfs(i, j);
            answer.push_back(cnt);
           }
        }
    }

    // 정리
    cout << answer.size() << endl;
    sort(answer.begin(), answer.end());
    for(int i = 0; i < answer.size(); i++) {
        cout << answer[i] << endl;
    }
    return 0;
}