반응형
출처 => [알고리즘 해결을 위한 창의적 알고리즘 해결 (중급)]
문제
문제 분석
문제의 의도: 단순 비선형 탐색이 아니라, 두더지 굴을 나타내는 숫자인 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();
}
728x90
반응형
'💻 개인공부 💻 > 알고리즘' 카테고리의 다른 글
[백준 - 2178] 미로 탐색 (feat. 너비우선탐색) / C++ (0) | 2020.07.03 |
---|---|
[백준 - 2267] 단지번호붙이기 (feat. 깊이우선탐색) / C++ (0) | 2020.07.03 |
[acmicpc] upper bound (feat. 이진 검색 알고리즘) / C++ (0) | 2020.06.08 |
백준) 2 x n 타일링 (재귀함수) / JAVA (0) | 2020.04.17 |
백준) - 1로 만들기(재귀함수) / C++ (0) | 2020.04.13 |