BOJ)2677 단지번호붙이기

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

DFS를 이용하여 풀이하였다.

동서남북 방향 중, map[y][x] = 1 && visited[y][x] = 0 인 조건일 때, 움직일 수 있다.

방문한 지점들을 카운트 해주며, 시작지점으로부터의 'DFS 사이클'이 끝나면 res에 카운트되어진 값을 넣어준다. 

#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; int map_size; int map[26][26] = { 0 }; char row[26] = { 0 }; int visited[26][26] = { 0 }; vector <int> res; int cnt=0; void DFS(int y, int x) { cnt++; visited[y][x] = 1; if (map[y + 1][x] == 1 && visited[y + 1][x] == 0) DFS(y + 1, x);//남 if (map[y - 1][x] == 1 && visited[y - 1][x] == 0) DFS(y - 1, x);//북 if (map[y][x+1] == 1 && visited[y][x+1] == 0) DFS(y, x+1);//동 if(map[y][x-1] == 1 && visited[y][x-1] == 0) DFS(y, x-1);//서 } int main() { cin >> map_size; for (int i = 0; i < map_size; i++) { cin >> row; for (int j = 0; j < map_size; j++) { map[i][j] = row[j]-'0'; } } for (int i = 0; i < map_size; i++) { for (int j = 0; j < map_size; j++) { if (map[i][j] == 1 && visited[i][j] == 0) { DFS(i, j); res.push_back(cnt); cnt = 0; } } } cout << res.size() << "\n"; sort(res.begin(), res.end()); for (auto i : res) { cout << i << "\n"; } return 0; }