Notice
Recent Posts
Recent Comments
Link
복's
[ LeetCode - 1267 ] Count Servers that Communicate 본문
728x90
https://leetcode.com/problems/count-servers-that-communicate/
Count Servers that Communicate - LeetCode
Can you solve this real interview question? Count Servers that Communicate - 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 server
leetcode.com
속도가 다른 코드들에 늦는 이유는 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
[ 📌 결과 ]
728x90
'알고리즘 > LeetCode' 카테고리의 다른 글
[ LeetCode - 28 ] Find the Index of the First Occurrence in a String (2) | 2023.11.01 |
---|---|
[ LeetCode - 27 ] Remove Element (0) | 2023.11.01 |
[ LeetCode - 1275 ] Find Winner on a Tic Tac Toe Game (2) | 2023.11.01 |
[ LeetCode - 19 ] Remove Nth Node From End of List (0) | 2023.10.31 |
[ LeetCode - 17 ] Letter Combinations of a Phone Number (1) | 2023.10.31 |