[Programmers] Rete (Python)

Problema

Una rete e’ una forma di connessione in cui i computer possono scambiare informazioni tra loro. Ad esempio, se il computer A e’ direttamente connesso al computer B, e il computer B e’ direttamente connesso al computer C, allora anche il computer A e il computer C possono scambiare informazioni indirettamente. Quindi i computer A, B e C sono tutti sulla stessa rete.

Dato il numero di computer n e un array 2D computers contenente le informazioni sulle connessioni, scrivere una funzione solution che restituisca il numero di reti.

Vincoli:

• n e’ un numero naturale tra 1 e 200.
• Ogni computer e’ rappresentato da un intero da 0 a n-1.
• Se il computer i e il computer j sono connessi, computers[i][j] vale 1.
• computer[i][i] e’ sempre 1.

Soluzione

1
def dfs(computers, v, visited):
2
    visited[v] = True
3

4
    for node in range(len(computers)):
5
        if visited[node] == False and computers[v][node] == 1:
6
            dfs(computers, node, visited)
7

8

9
def solution(n, computers):
10
    answer = 0
11
    visited = [False] * n
12

13
    for v in range(n):
14
        if not visited[v]:
15
            dfs(computers, v, visited)
16
            answer += 1
17
    return answer

Si tratta di DFS dato che e’ una funzione ricorsiva che continua a esplorare l’array computers in profondita’. Inizialmente avevo provato a risolverlo modificando direttamente i valori di computers, ma non ci sono riuscito.

Il punto chiave e’ che anche se computers e’ un array 2D, si stanno comunque attraversando n vertici. Non bisogna farsi confondere dall’array 2D — basta cercare attraverso gli n vertici.

Si usano gli n vertici come righe e si attraversa computers di conseguenza.