(BOJ) 2667 풀이

#include<iostream>
#include<stdio.h>
#include <algorithm>
using namespace std;
int map[26][26]={0,};
int visit[26][26]={0,};
int yy[]={0,-1,0,1};
int xx[]={-1,0,1,0};
int N;

int DFS(int y,int x,int c){
    if (y < 0 || x < 0 || y >= N || x >= N || map[y][x] == 0) return 0;
    visit[y][x]=1;
    for(int asdf=0;asdf<4;asdf++){
        int nx=x+xx[asdf];
        int ny=y+yy[asdf];
        if(map[ny][nx]&&!visit[ny][nx]){
            visit[ny][nx]=1;
            c=DFS(ny,nx,c+1);
        }
    }    
    return c;
}
int main(){
    int house=0;
    int houses[25*25]={0,};
    scanf("%d",&N);
    for(int j=0;j<N;j++){
        for(int i=0;i<N;i++){
            scanf("%1d",&map[j][i]);
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]&&!visit[i][j]){
                // cout << '(' << i << ',' << j << ')' << endl;
                houses[house++]=DFS(i,j,1);
                // exit(0);
            }
        }
    }
    sort(houses,houses+house);
    cout << house << endl;
    for(int i=0;i<house;i++){
        cout << houses[i] << endl;
    }
}

솔브코드입니다.

출처 boj

이렇게 입력이 주어지는데,

0,0 부터 N-1,N-1 까지 DFS 반복문을 돌리면서

해당 블록을 재귀함수로 돌며 3번째 인자값을 1씩 증가시키면서

마지막 리턴값을 houses 배열에 저장합니다.

DFS 함수의 c=DFS(~~,c+1) 에 대해 간단히 설명을 해보면,

첫 호출 시, DFS 에서 각각의 방향 (상하좌우) 로 검사를 하고, c+1 을 인자로 넘겨주며 호출을 한 뒤, 탐색한 결과를 c 에 업데이트 하고 , 그 c값 +1 을 다음 방향으로 호출할 때 인자로 주며 다시 리턴값으로 c 를 업데이트 해서 결국 구역 내 모든 집의 수가 나옵니다.

houses 배열 크기를 적어도 25*25 정도로 줘야하는데 25로 줘서

자꾸 oob 가 발생하는데 이유를 몰랐었다.