99클럽 코테 스터디 15일차 TIL + 네트워크

유니온 파인드를 사용한 풀이

## 유니온 파인드로 한번 풀어보자
## 마지막 한 번 씩 다시 find_parent 해야하는 이유
## https://school.programmers.co.kr/questions/55001

def find_parent(x, parent):
    if x!=parent[x]:
        x = find_parent(parent[x], parent)
    return parent[x]

def union(a,b,parent):
    a=find_parent(a, parent)
    b= find_parent(b, parent)
    if a<b: 
		    ## (큰 쪽 Node(b)의 부모값 = 작은 쪽 node (a) 값)
        parent[b]=a
    else:
        parent[a]=b

def solution(n, computers):
    answer = 0
    parent = [i for i in range(n+1)]
    
    
    for a in range(1, n+1):
        for b in range(1, n+1):
            if computers[a-1][b-1] and (find_parent(a,parent)!=find_parent(b,parent)):       
                union(a,b,parent)
    ans = set()

    for x in range(1, n+1):
        ans.add(find_parent(x, parent))

    return len(ans)

bfs를 사용한 풀이

from collections import deque

def solution(n, computers):
    visited=[False]*(n)
    
    def bfs(start):
        que = deque()
        que.append(start)
        visited[start]=True
        while que:
            x = que.popleft()
            for y in range(n):
                if x==y or visited[y] or not(computers[x][y]):
                    continue
                que.append(y)
                visited[y]=True
    count = 0
    for x in range(n):
        if not(visited[x]):
            count+=1
            bfs(x)

    return count

dfs를 사용한 풀이

def solution(n, computers):
    visited = [0]*(n)
    group = [-1]*(n)
    g = 0
    def dfs(start, g):
        ## print(start, g, visited, group)
        if sum(visited)==n:
            return
        for end in range(n):
            if start!=end and computers[start][end] and not(visited[end]):
                group[end]=g
                visited[end]=1
                dfs(end, g)
        
    for i in range(n):
        if not(visited[i]):
            g+=1
            group[i]=g
            visited[i]=1
            dfs(i,g)
    ##3 print(group)
    return len(set(group))