C++로 통신 타워 그룹 개수 구하는 프로그램 – DFS 알고리즘 풀이

문제 정의

2차원 이진 행렬이 주어졌다고 가정해 봅시다. 여기서 1은 통신 타워가 설치된 셀을, 0은 빈 셀을 나타냅니다. 타워들은 다음 두 가지 규칙에 따라 서로 통신할 수 있습니다.

1. 직접 통신: 타워 A와 타워 B가 같은 행 또는 같은 열에 위치하면 서로 직접 통신할 수 있습니다.
2. 간접 통신(추이성): 타워 A가 B와 통신할 수 있고, B가 C와 통신할 수 있다면 A 역시 C와 통신할 수 있습니다.

우리의 목표는 서로 통신 가능한 타워들의 집합, 즉 그룹이 총 몇 개인지 구하는 것입니다.

예시 입력

위 행렬에는 타워가 (0,0), (0,1), (1,2), (2,0), (2,2) 위치에 있습니다. (0,0)과 (0,1)은 같은 행에, (2,0)과 (2,2)는 같은 행에, (1,2)와 (2,2)는 같은 열에 있으므로 추이성에 의해 모든 타워가 하나의 그룹으로 연결됩니다. 따라서 정답은 1입니다.

풀이 접근 방식: DFS 활용

이 문제는 그래프의 연결 요소(Connected Component) 개수를 세는 것과 동일한 구조입니다. 깊이 우선 탐색(DFS)을 사용하면 효율적으로 해결할 수 있습니다.

1. dfs() 함수를 정의합니다. 이 함수는 2차원 배열 matrix와 좌표 i, j, 그리고 행렬의 크기 n, m을 매개변수로 받습니다.
2. 방문 처리를 위해 matrix[i][j] 값을 2로 변경합니다.
3. k를 1부터 n-1까지 증가시키며, p := (i + k) mod n, q := j로 설정합니다. matrix[p][q]가 1이라면 해당 위치에서 dfs()를 재귀 호출합니다. (같은 열에 있는 모든 타워 탐색)
4. k를 1부터 m-1까지 증가시키며, p := i, q := (j + k) mod m으로 설정합니다. matrix[p][q]가 1이라면 dfs()를 재귀 호출합니다. (같은 행에 있는 모든 타워 탐색)
5. 메인 solve() 함수에서는 n := 행렬의 행 개수, m := 행렬의 열 개수, ans := 0으로 초기화합니다.
6. 모든 셀을 순회하면서 matrix[i][j]가 1인 경우 ans를 1 증가시키고 dfs(matrix, i, j, n, m)을 호출하여 연결된 모든 타워를 하나의 그룹으로 방문 처리합니다.
7. 순회가 끝나면 ans를 반환합니다.

핵심 아이디어는 이미 방문한 셀을 2로 표시해 중복 탐색을 방지하는 것입니다. 새로운 미방문 타워(값이 1인 셀)를 발견할 때마다 그룹 수를 하나 늘리고, DFS로 해당 그룹에 속한 모든 타워를 한 번에 처리합니다.

C++ 구현 예제

#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

복잡도 분석

• 시간 복잡도: 각 타워 셀마다 자신이 속한 행과 열 전체를 한 번씩 스캔하므로 O(N × M × (N + M))입니다.
• 공간 복잡도: 재귀 호출 스택을 포함하여 O(N × M)입니다.