[acmicpc] 두더지 굴 (feat. 깊이우선탐색 알고리즘) / C++

출처 => [알고리즘 해결을 위한 창의적 알고리즘 해결 (중급)]

 

 

문제

 

문제 분석

문제의 의도: 단순 비선형 탐색이 아니라, 두더지 굴을 나타내는 숫자인 1을 중심으로 상,하,좌, 우에 1이 있다면 이 부분에 간선이 있는 것으로 생각한다. 

(0,0)에서 순차 탐색을 하여 그 값이 1이라면 그 점을 중심으로 깊이우선탐색을 하여 모든 연결된 점을 방문한다.

 

풀이

이런 식으로 마지막 칸까지 진행을 한다면 다음과 같은 결과가 나온다. 

=> 따라서 각 굴의 크기는 7, 8, 9라는 사실을 알 수 있다.

 

 

소스코드 & 결과

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

int n, A[101][101], cnt, Size[101];


void input() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> A[i][j];
}
void output() {
	cout << cnt;
	for (int i = 0; i < cnt; i++) {
		cout << Size[i] << endl;
	}
}

bool safe(int a, int b) {
	return (0 <= a && a < n) && (0 <= b && b < n);
}
bool cmp(int a, int b) {
	return a > b;
}

void dfs(int a, int b, int c) {
	A[a][b] = c;
	if (safe(a + 1, b) && A[a + 1][b] == 1)
		dfs(a + 1, b, c);
	if (safe(a - 1, b) && A[a - 1][b] == 1)
		dfs(a - 1, b, c);
	if (safe(a, b + 1) && A[a][b + 1] == 1)
		dfs(a, b + 1, c);
	if (safe(a, b - 1) && A[a][b - 1] == 1)
		dfs(a, b - 1, c);
}

void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (A[i][j] == 1)
				cnt++;
			dfs(i, j, cnt + 1);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (A[i][j])
				Size[A[i][j] - 2]++;
			sort(Size, Size + cnt, cmp);
		}
	}
}

int main() {
	input();
	solve();
	output();
}