[leetcode][1267] Count Servers that Communicate

문제 : https://leetcode.com/problems/count-servers-that-communicate/

---

m x n grid가 주어질 때, 1은 서버, 0은 빈 셸이라고 하자.

같은 행이나 열에 서버가 있는 경우 그 서버는 다른 서버와 통신할 수 있다고 한다.

다른 서버와 통신할 수 있는 서버의 총 개수를 구하는 문제이다.

---

예를 들어서 확인해보자. 

1	1	0	0
0	0	1	0
0	0	1	0
0	0	0	1

grid가 위와같이 주워졌다고 하자.

1	1	0	0
1	1	1	0
1	1	2	0
1	1	2	1

열 subsum은 위와 같이 채워진다. 위에서 아래로 채운다고 생각하면 된다.

1	2	2	2
0	0	1	1
0	0	1	1
0	0	0	1

행 subsum은 위와 같이 채워진다. 왼쪽에서 오른쪽으로 채운다고 보면된다.

 

말은 subsum을 구한다고 했지만 총 결과만 보면된다. 

즉, 각 행이나 열이 가지고 있는 서버의 개수만 본다. 빨간색 글자만 저장해두면 된다.

 

만약 (0,1) 서버가 다른 서버와 통신을 하는지 알고 싶으면 행[0] 열[1] 값 중 하나라도 2 이상이라면 다른 서버와 통신할 수 있다고 볼 수 있다. 행[0], 열[1]이 모두 1인 경우 (0,1)에 있는 서버는 해당 행, 열에 자신밖에 없는 경우이기 때문에 다른 서버와 통신할 수 없다.

 

시간복잡도는 모든 grid를 2번 탐색하므로 O(NM)이다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1267.%20Count%20Servers%20that%20Communicate.cpp