https://www.acmicpc.net/problem/1012
1. 문제 접근
MxN 밭에서 1로표시된 군집의 갯수를 세는 문제이다. 여기서 군집이란 문제의 설명처럼 인접한 배추들을 말한다. 이러한 인접한 원소를 다루는 문제는 BFS나 DFS를 생각할 수 있는데 해당문제는 어느것을 사용하여도 풀수 있으나 필자는 재귀함수를 이용한 DFS를 사용하였다.
시간복잡도 계산
MxN 밭의 모든 위치에서 인접한 방향을 검색해야하는 경우가 최악의 경우이므로 시간복잡도는 아래와 같이 계산해 볼 수 있다. 이는 주어진시간 1초동안 너무나 충분한 계산 횟수이기에 위 방법을 사용하여 문제를 풀어보았다.
시간복잡도 = M x N x 4(인접한 방향 갯수) = 10,000
2. 코드
#include<iostream>
using namespace std;
#define MAX_MN 50
int cir_m[4] = { -1, 0, 1, 0 };
int cir_n[4] = { 0, 1, 0, -1 };
int check(int loc[][MAX_MN], int checked[][MAX_MN], int m, int n, int mSize, int nSize) {
if (m < 0 || n < 0 || m >= mSize || n >= nSize)
return 0;
if (loc[m][n] == 0 || checked[m][n] == 1)
return 0;
checked[m][n] = 1;
for (int i = 0; i < 4; i++)
check(loc, checked, m + cir_m[i], n + cir_n[i], mSize, nSize);
return 1;
}
void init(int loc[][MAX_MN], int checked[][MAX_MN], int m, int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
loc[i][j] = 0;
checked[i][j] = 0;
}
}
}
int main() {
int T;
int M, N, K;
int cabLoc[MAX_MN][MAX_MN] = { 0, };
int checked[MAX_MN][MAX_MN] = { 0, };
cin >> T;
for (int t = 0; t < T; t++) {
cin >> M >> N >> K;
init(cabLoc, checked, M, N);
for (int i = 0; i < K; i++) {
int mK, nK;
cin >> mK >> nK;
cabLoc[mK][nK] = 1;
}
int bugCount = 0;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
if (check(cabLoc, checked, i, j, M, N) == 1)
bugCount++;
cout << bugCount << endl;
}
return 0;
}
'개발하고 > 코딩테스트' 카테고리의 다른 글
[백준] 1008번 A/B (0) | 2021.08.02 |
---|---|
[백준] 1003번 피보나치 함수 (0) | 2021.08.02 |
[백준] 1002번 터렛 (0) | 2021.08.02 |
[백준] 1018번 체스판 다시 칠하기 (0) | 2021.07.31 |
[백준] 1026번 보물 (0) | 2021.07.30 |