# 백준 : 단지번호붙이기 (2667)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_2667_putnumberofstreet)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

int N;
int map[26][26];
int visit[26][26];
int result[400];
int idx;
       
void DFS(int y, int x, int idx) {
    visit[y][x] = 1;
    //cout<<"("<<y<<" , "<<x<<")"<<" -> ";
    result[idx]++;
    if((y > 0) && map[y - 1][x] && !visit[y - 1][x]) {
        DFS(y - 1, x, idx);
    }
    if((y < N - 1) && map[y + 1][x] && !visit[y + 1][x]) {
        DFS(y + 1, x, idx);
    }
    if((x > 0) && map[y][x - 1] && !visit[y][x - 1]) {
        DFS(y, x - 1, idx);
    }
    if((x < N - 1) && map[y][x + 1] && !visit[y][x + 1]) {
        DFS(y, x + 1, idx);
    }
}

int main(void)
{
    string value;
    cin>>N;
    for(int i = 0; i<N; i++) {
        cin>>value;
        for(int j=0; j<N; j++) {
            map[i][j] = value[j] - 48;
        }
    }
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(map[i][j] && !visit[i][j])   DFS(i, j, idx++);
        }
    }
    sort(result, result + idx);
    cout<<idx<<endl;
    for(int i=0; i<idx; i++) cout<<result[i]<<endl;
    
    return 0;
}

풀이

하앍 도대체 몇시간만에 풀어낸건지.
사실 아이디어는 대충 생각해냈는데 1초라는 제한시간에 쫄아서 DP로 풀려고 뻘짓을 어마어마하게 했다.
이 문제를 DP로 풀을 수도 있긴 했는데.. 문제는 몇개의 단지로 나누어지는지 구하기가 힘들어서..
BFS는 종료 조건을 구하는게 힘들고.. 그래서 DFS로 구했는데 쉽게 풀리네.?

푸는데 너무 진을 뺏더니 풀이쓰는게 힘들다.
소스 코드를 자세히 보면 어렵지 않게 풀 수 있을것 같으므로 해설은 생략.. 해도 되겠죠..?