[백준]: 2667번: 단지번호붙이기 / DFS 경로찾기

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

이 문제는 전형적인 DFS의 경로찾기 문제라고 볼 수 있다.

DFS의 기본적인 로직을 안다면 빠르게 해결할 수 있는 문제. 

#include<iostream>

using namespace std;

#include<algorithm>

#include<cstring>

int apartment[30][30];

int apartment_cnt[30];

bool visited[30][30];

int n, cnt, ans, k;

int xx[4] = { 0,1,0,-1 };

int yy[4] = { -1,0,1,0 };

void dfs(int x, int y)

{

if (x >= n || y >= n)return;//종료조건

visited[x][y] = true;

for (int i = 0; i < 4; i++)

{

int nx = x + xx[i];

int ny = y + yy[i];

if (nx >= 0 && ny >= 0 && !visited[nx][ny] && apartment[nx][ny])

{

cnt++;

dfs(nx, ny);

}

}

}

int main()

{

cin >> n;

k = 0;

int a;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

scanf("%1d", &apartment[i][j]);

}

}

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

cnt = 0;

if (!visited[i][j] && apartment[i][j])

{

ans++;

cnt++;

dfs(i, j);

apartment_cnt[k++] = cnt;

}

}

}

sort(apartment_cnt, apartment_cnt + k);

cout << ans << "\n";

for (int i = 0; i < k; i++)

{

cout << apartment_cnt[i] << "\n";

}

return 0;

}