네트워크
문제 파악
주어진 컴퓨터들 간의 연결 정보를 바탕으로 독립된 네트워크의 수를 구하는 문제이다.
접근 방법
모든 컴퓨터에 대해 DFS를 수행하여 독립된 네트워크의 수를 센다
- 방문 여부를 나타내는 배열
visited
를 선언 - 모든 컴퓨터를 순회하며, 아직 방문하지 않은 컴퓨터를 시작점으로 DFS를 수행한다.
- DFS를 통해 한 네트워크를 방문하면서 해당 네트워크에 속한 모든 컴퓨터를 방문했음을 표시한다.
코드 구현
def solution(n, computers):
def dfs(node):
visited[node] = True
for next_node in range(n):
if not visited[next_node] and computers[node][next_node] == 1:
dfs(next_node)
return
count = 0
visited = [False] * n
for computer in range(n):
if not visited[computer]:
dfs(computer)
count += 1
return count
Leave a comment