[코딩테스트C++] 단지번호붙이기

오늘의 문제

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

단지번호붙이기

나의풀이

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 25
using namespace std;

// 단지번호
int map[MAX][MAX] ={0, };
bool check[MAX][MAX] = {false, };
int dn[4] = {-1, 1, 0, 0};
int dm[4] = {0, 0, 1, -1};
int size;

int dfs(int N, int M){
    int answer = 0;
    check[N][M] = true;
    for(int j=0;j<4;j++){
        int n = N + dn[j];
        int m = M + dm[j];
        if(n >= size || n < 0 || m >= size || m < 0)
            continue;
        if(check[n][m] == false && map[n][m] == 1)
            answer += dfs(n, m);
    }
    return answer + 1;
}

풀이 법

• DFS를 이용해서 그래프를 탐색, 한번 탐색한 곳은 다시탐색 않고 1이 있는 구역을 모두 찾아옴
• return 은 다녀온 노드의 수에 1(자기자신)을 더하여 값을 return 함
• 그렇게 return 된 값이 단지 내의 집의 개수 => vector에 넣고 정렬한다.

모범 답안

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

int N,cnt=0;
int arr[25][25];

void dfs(int x,int y)
{
	int i,xx,yy;
	int dx[4]={0,0,1,-1};
	int dy[4]={1,-1,0,0};
	arr[x][y]=0;
	cnt++;
	for (i=0;i<4;i++)
	{
		xx=x+dx[i];
		yy=y+dy[i];
		if (xx>=0&&yy>=0&&xx<N&&yy<N&&arr[xx][yy]==1)
		{
			dfs(xx,yy);
		}
	}
	
}

int main()
{
	int i,j,s=0;
	int count[316];
	scanf("%d",&N);
	for (i=0;i<N;i++)
	{
		for (j=0;j<N;j++)
		{
			scanf("%1d",&arr[i][j]);
		}
	}
	for (i=0;i<N;i++)
	{
		for (j=0;j<N;j++)
		{
			if (arr[i][j]==1){
				dfs(i,j);
				count[s]=cnt;
				cnt=0;
				s++;
			}
		}
	}
	sort(count,count+s);
	printf("%d\n",s);
	for (i=0;i<s;i++)
	{
		printf("%d\n",count[i]);
	}
	return 0;
}