Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 네트워크

[네트워크]

• 인접 행렬을 입력받아 연결 요소의 개수를 세는 문제이다. BFS, Non-recursive DFS, Recursive DFS, Union-Find의 구현을 연습해보기 좋다.

Solution 1. Recursive DFS $O(n^2 + V+E)$

def dfs(v, adj, visited):
    visited.add(v)

    for nxt in adj[v]:
        if nxt not in visited:
            dfs(nxt, adj, visited)
    
    return 1

def solution(n, computers):
    adj = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i<j and computers[i][j]:
                adj[i].append(j)
                adj[j].append(i)
    
    visited = set()
    return sum(dfs(v, adj, visited) for v in range(n) if v not in visited)

• 한 번의 DFS가 끝났다는 것은 연결 요소들에 대해 모두 순회했다는 뜻이므로 1을 반환하고, 아직 방문하지 않은 노드들에 대해 DFS를 하면서 이 값을 누적시키는 것이 연결 요소의 개수이다.

Solution 2. Non-Recursive DFS $O(n^2+V+E)$

def dfs(v, adj, visited):
    stack = [v]
    visited.add(v)

    while stack:
        for nxt in adj[stack.pop()]:
            if nxt not in visited:
                stack.append(nxt)
                visited.add(nxt)
    
    return 1

def solution(n, computers):
    adj = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i<j and computers[i][j]:
                adj[i].append(j)
                adj[j].append(i)
    
    visited = set()
    return sum(dfs(v, adj, visited) for v in range(n) if v not in visited)

• 비재귀 DFS이다.

Solution 3. BFS $O(n^2+V+E)$

def bfs(v, adj, visited):
    queue = deque([v])
    visited.add(v)

    while queue:
        for nxt in adj[queue.popleft()]:
            if nxt not in visited:
                queue.append(nxt)
                visited.add(nxt)
    
    return 1

def solution(n, computers):
    adj = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i<j and computers[i][j]:
                adj[i].append(j)
                adj[j].append(i)
    
    visited = set()
    return sum(bfs(v, adj, visited) for v in range(n) if v not in visited)

Solution 4. Union-Find $O(n^2 \cdot \alpha(n)) \approx O(n^2)$

def find(p, x):
    if p[x] < 0: return x
    p[x] = find(p, p[x])
    return p[x]

def union(p, x, y):
    xs, ys = find(p, x), find(p, y)
    if xs == ys: return

    if p[xs] < p[ys]:
        p[ys] = xs
    else:
        if p[xs] == p[ys]:
            p[ys] -= 1
        p[xs] = ys

def solution(n, computers):
    p = [-1]*n

    for i in range(n):
        for j in range(n):
            if i<j and computers[i][j]:
                union(p, i, j)
    
    return sum(p[v] < 0 for v in range(n))

---