1이 통신 타워를 나타내고 0이 빈 셀을 나타내는 2D 이진 행렬이 있다고 가정합니다. 타워는 다음과 같은 방식으로 통신할 수 있습니다. 1. 타워 A와 타워 B가 같은 행이나 열에 있는 경우 서로 통신할 수 있습니다. 2. 타워 A가 타워 B와 대화할 수 있고 B가 C와 대화할 수 있다면 A는 C와 대화할 수 있습니다(전이 속성). 우리는 거기에 있는 총 타워 그룹의 수를 찾아야 합니다(여기서 그룹은 서로 대화할 수 있는 타워 목록입니다).
따라서 입력이 다음과 같으면
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
dfs() 함수를 정의합니다. 이것은 하나의 2D 배열 행렬, i, j, n, m,
를 취합니다. -
행렬[i, j] :=2
-
초기화 k :=1의 경우 k
-
p :=(i + k) 모드 n
-
q :=j
-
행렬[p, q]가 1과 같으면:
-
dfs(행렬, p, q, n, m)
-
-
-
k:=1 초기화의 경우 k
-
피 :=나는
-
q =(j + k)
-
행렬[p, q]가 1과 같으면:
-
dfs(행렬, p, q, n, m)
-
-
-
기본 방법에서 다음을 수행합니다.
-
n :=행렬의 크기
-
답변 :=0
-
initialize i :=0의 경우 i
-
j 초기화의 경우:=0, j
-
행렬[i, j]가 1과 같으면:
-
(1만큼 증가)
-
dfs(행렬, i, j, n, m)
-
-
-
-
반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(vector<vector<int>>& matrix, int i, int j, int& n, int& m) {
matrix[i][j] = 2;
for (int k = 1; k < n; k++) {
int p = (i + k) % n, q = j;
if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
}
for (int k = 1; k < m; k++) {
int p = i, q = (j + k) % m;
if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
}
}
int solve(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1) {
ans++;
dfs(matrix, i, j, n, m);
}
}
}
return ans;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
main(){
vector<vector<int>> v = {
{1,1,0},
{0,0,1},
{1,0,1}
};
cout << solve(v);
} 입력
{{1,1,0},
{0,0,1},
{1,0,1}}; 출력
1