(Python3) - LeetCode (Medium) : 1267. Count Servers that Communicate

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

구현 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

다음 변수를 선언합니다.

📑 행 길이 rows, 열 길이 cols, 정답 변수 can_communicate, 방문여부 배열 ck를 선언 후 적절히 초기화합니다.

📔 풀이과정

📑 grid의 원소를 순회

• 현재 행에 대해 수평으로, 현재 열에 대해 수직으로 server개수를 세줍니다.

📑 방문하지 않았고 통신 가능한 server 개수 세기

• 세준 서버의 개수가 1개를 초과한다면 통신이 가능합니다.
• 해당 조건을 만족한다면 다시 현재 행에 대해 수평으로, 현재 열에 대해 수직으로 방문하지 않은 server개수를 세주며 방문해줍니다.
• 방문하지 않은 server 개수를 can_communicate에 더해줍니다.

📑 시간 복잡도

2차원으로 grid를 순회하며 수평, 수직으로 통신 가능한 server 수를 세야 하므로 O(N^3)으로 순회 가능합니다.

📑 공간 복잡도

2차원 ck배열이 가장 많은 공간을 추가적으로 차지하므로 O(N^2)가 됩니다.

📔 정답 출력 | 반환

can_communicate를 반환합니다.

---

📕 Code

📔 Python3

from collections import deque 

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        can_communicate = 0
        ck = [[0 for _ in range(cols)] for _ in range(rows)]

        def count_row_server(start_row:int) -> int:
            count = 0
            for c in range(cols):
                if grid[start_row][c] == 1:
                    count += 1
            return count

        def count_col_server(start_col:int) -> int:
            count = 0
            for r in range(rows):
                if grid[r][start_col] == 1:
                    count += 1
            return count

        def check_rows(start_row:int):
            count_unchecked = 0
            for r in range(rows):
                if ck[r][j] == 0 and grid[r][j] == 1:
                    ck[r][j] = 1
                    count_unchecked += 1
            return count_unchecked

        def check_cols(start_col:int):
            count_unchecked = 0
            for c in range(cols):
                if ck[i][c] == 0 and grid[i][c] == 1:
                    ck[i][c] = 1
                    count_unchecked += 1
            return count_unchecked

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 0:
                    continue

                row_count = count_row_server(i)
                col_count = count_col_server(j)

                if row_count + col_count - 1 > 1:
                    can_communicate += check_rows(i)
                    can_communicate += check_cols(j)

        return can_communicate

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.