[ LeetCode - 1267 ] Count Servers that Communicate

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

Count Servers that Communicate - LeetCode

속도가 다른 코드들에 늦는 이유는 graph 풀이가 아니라 주어진 grid에서 row의 합과 column의 합을 구해서 1보다 클 경우 이어져 있다고 판단하는 풀이가 있어서 graph는 느릴 수 밖에 없는 것 같다.

---

[ 📌 풀이 ]

• 주어진 grid를 그대로 사용하며 방문 체크는 grid가 0, 1로 이루어져 있기 때문에 -1로 변경해서 사용
• 맨 처음 시작 노드는 bfs로직 시작 시 방문 체크를 하지않고 시작함 (밑에 그림과 함께 설명)
• 노드 방문시 해당 노드 기준으로 횡과 축에 존재하는 '1' 값을 가진 노드들 전부 방문

[ 방문 체크 시각화 ]

만약 bfs로직 들어가면서 방문을 체크한다면 코드로는 밑처럼 되는데

def bfs(self, grid: List[List[int]],x:int, y:int) -> int:
        queue = deque()
        queue.append((x, y))
        cnt = 0
        grid[x][y] = -1 <=== 방문 체크

그림 위를 보면 방문 체크하고 넘어가면 다시 돌아오지 못해서 횡에 있는 노드를 방문할 수 없게 된다.

그림 밑처럼 되려면 방문 체크는 while문 로직 안에서 수행되어야 한다.

---

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.11.01(Wed)
# Spend Time: 미측정
# Runtime   : 1134 ms (Beats 5.14%)
# Memory    : 17.9 MB (Beats 84.89%)
# Algoritm  : Graph
"""

from typing import List
from collections import deque

class Solution:
    def countServers(self, grid: List[List[int]]) -> int:
        self.row, self.col = len(grid), len(grid[0])
        ans = 0
        
        for r in range(self.row):
            for c in range(self.col):
                if grid[r][c] == 1:    
                    ans += self.bfs(grid, r, c)

        return ans

    def bfs(self, grid: List[List[int]],x:int, y:int) -> int:
        queue = deque()
        queue.append((x, y))
        cnt = 0

        while queue:
            curX, curY = queue.popleft()

            for moveX, moveY in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                newX = moveX + curX
                newY = moveY + curY

                while self.isValid(newX, newY) and grid[newX][newY] != 1:
                    newX += moveX
                    newY += moveY

                if self.isValid(newX, newY) and grid[newX][newY] == 1:
                    cnt +=1
                    grid[newX][newY] = -1
                    queue.append((newX, newY))

        return cnt

    def isValid(self, x:int, y:int) -> bool:
        return 0 <= x < self.row and 0 <= y < self.col

---

[ 📌 결과 ]

[ Result ]