래원

[LeetCode] 1267. Count Servers that Communicate (Python) 본문

알고리즘/LeetCode

[LeetCode] 1267. Count Servers that Communicate (Python)

Laewon Jeong 2025. 1. 23. 13:30

 

 

난이도: Medium

문제 설명


You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server.

 

문제 예제


Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

 

Example 2:

 

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

 

Example 3:

 

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. 
The two servers in the third column can communicate with each other. 
The server at right bottom corner can't communicate with any other server.

 

제한사항


  • m == grid.length
  • n == grid[i].length
  • 1 <= m <= 250
  • 1 <= n <= 250
  • grid[i][j] == 0 or 1

 

Solution(솔루션)


def get_answer(row_or_col, n, s):
    for i in range(n):
        if len(row_or_col[i]) >= 2:
            for loc in row_or_col[i]:
                s.add(loc)

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        check = defaultdict(bool)

        row = [[] for _ in range(n)]
        col = [[] for _ in range(m)]

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    row[i].append((i,j))
                    col[j].append((i,j))
        
        s = set()
        get_answer(row, n, s)
        get_answer(col, m, s)
        
        return len(s)

 

처음에는 상하좌우로 이어져있는 서버에 수를 구하라라는 건 줄 알고 그렇게 풀었는데 Wrong Answer라고 알려주었다...

 

그래서 문제를 다시 보니 같은 row에 있거나 같은 column에 있으면 communication이 가능하다는 것을 알게 되었다.

 

그래서 코드를 다시 짜기 시작했다.

 

먼저 server가 있는 위치를 row와 col리스트를 각각 저장했다.

 

예를들어, grid = [[1,0], [1,1]]과 같을 때 row와 col은 다음과 같이 저장된다.

 

여기서 이제 len(row[i]) 또는 len(col[i])가 2이상이면 이를 세면 된다. 

 

하지만 위 그림에서 그냥 count하게되면 4라는 답이 나오지만 원하는 답은 3이다.

 

이는 row와 col에서 중복된 위치(위 그림에서 (1,0))도 같이 count하기 때문에 그렇다.

 

따라서, set을 이용해 중복된 위치를 제거해주었다.

 

마지막에는 set의 길이를 반환하여 정답을 맞출 수 있었다.


문제: 1267. Count Servers that Communicate

 

깃허브: github

 

algorithmPractice/LeetCode/1396-count-servers-that-communicate at main · laewonJeong/algorithmPractice

하루 한 문제 챌린지. Contribute to laewonJeong/algorithmPractice development by creating an account on GitHub.

github.com