[백준/C++]#2667 - 단지번호붙이기

풀이

#include <cstdio>
#include <algorithm>
using namespace std;

int a[26][26];
int check[26][26];
int dx[] = {0, 0, 1, -1};	// 상하좌우 + 1
int dy[] = {1, -1, 0, 0};
int ans[25*25];
int n;
	
void dfs(int x, int y, int CNT) {
	check[x][y] = CNT;
	for (int k=0; k<4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (0 <= nx && nx < n && 0 <= ny && ny < n) {	// 배열의 범위를 넘어서지 않을 때
			if (a[nx][ny] == 1 && check[nx][ny] == 0) {
				dfs(nx, ny, CNT);
			}
		}
	}
		
}

int main() {
	scanf("%d", &n);
	for (int i=0; i<n; i++) {		// 입력
		for (int j=0; j<n; j++) {
			scanf("%1d", &a[i][j]);
		}
	}
	int cnt=0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (a[i][j] == 1 && check[i][j] == 0) {
				dfs(i, j, ++cnt);
			}
		}
	}
	printf("%d\n", cnt);
	for (int i=0; i<n; i++) {		// 각 단지의 수 계산
		for (int j=0; j<n; j++) {
			ans[check[i][j]]+=1;
		}
	}
	sort(ans+1, ans+cnt+1);		// 단지 수 정렬
	for (int i=1; i<=cnt; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

개념

입력이 붙어서 나올 때 (ex. 100101) C언어 문법을 통해 각각을 입력받을 수 있다.

scanf('%1d', &a[i][j]) 이와 같이 입력 받으면 1 자릿수만 입력받는다.

 

상하좌우를 참조하기 위한 방법으로 배열을 활용한다.

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

이를 사용해서 나타낸 if (0 <= nx && nx < n && 0 <= ny && ny < n) 는

없는 배열을 참조하여 발생하는 런타임오류를 막을 수 있다.

---

풀이

 

주어진 배열 값을 통해 탐색을 진행한다.

이번에는 1을 가진 배열의 상대적 위치가 중요하다

dfs가 무한 순환되지 않기 위해 check[26][26] 2차원 배열을 활용한다.

따라서 a[i][j]가 1이며 check[i][j]가 0일 경우, 탐색한다.

 

결국 main 함수 내에서는 2중 for문으로 모든 배열 인덱스를 확인해야한다.

++cnt로 main 함수 내에서 실행되는 dfs를 구분한다.

이 cnt 값은 check 배열에 대입되어 각 단지에 번호를 붙인다.

 

각 단지의 수를 구하는 법은, 마찬가지로 2중 for문을 사용한다.

check 배열의 값이 동일한 경우, 이를 ans 배열이 인덱스로 받아서 + 1 한다.

 

 

---

+a

 

다른풀이(from 백준github)

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int a[30][30];
int group[30][30];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int n;
int ans[25*25];
void bfs(int x, int y, int cnt) {
    queue<pair<int,int>> q;
    q.push(make_pair(x,y));
    group[x][y] = cnt;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int k=0; k<4; k++) {
            int nx = x+dx[k];
            int ny = y+dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (a[nx][ny] == 1 && group[nx][ny] == 0) {
                    q.push(make_pair(nx,ny));
                    group[nx][ny] = cnt;
                }
            }
        }
    }
}
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%1d",&a[i][j]);
        }
    }
    int cnt = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (a[i][j] == 1 && group[i][j] == 0) {
                bfs(i, j, ++cnt);
            }
        }
    }
    printf("%d\n",cnt);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            ans[group[i][j]]+=1;
        }
    }
    sort(ans+1, ans+cnt+1);
    for (int i=1; i<=cnt; i++) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

위의 방식이 재귀함수, 이 방식은 반복문을 활용한다.

그 외의 부분은 동일하다.