[프로그래머스] [union-find][bfs] 네트워크

네트워크

프로그래머스

 

• 내 풀이
  • union-find
  • 📍주의) union 하는 과정에서 이전에 union 된 값들도 모두 알맞게 고쳐줘야함
    • for문 돌려서 전부 재교체 하는 과정 가짐
    • -> 다 끝낸 후 마지막에 한번만 업데이트 해줘도됨

def solution(n, computers):
    def union(x,y):
        if find(x)<find(y):
            for i in range(len(root)):
                if root[i]==root[x]:
                    root[i]=root[y]
        else:
            for i in range(len(root)):
                if root[i]==root[y]:
                    root[i]=root[x]
        
    def find(x):
        if root[x]!=x:
            root[x]=find(root[x])
        return root[x]
    
    root=[x for x in range(n)]
    for i, computer in enumerate(computers):
        for j in range(n):
            if i==j: continue
            if computers[i][j]==0: continue
            union(i,j)
        
        
    return len(set(root))

 

• 다른 사람 풀이
  • 마지막에 한번에 업데이트

def solution(n, computers):
	def find(x):
        if x != root[x]:
            root[x]= find(root[x])
        return root[x]

    def union(a, b):
        a = find(a)
        b = find(b)

        if a < b:
            parents[b] = a
        else:
            parents[a] = b


    root = [i for i in range(n)]
    
    # computers 연결 정보에 따라 union
    for i in range(n):
        for j in range(n):
            if i == j or computers[i][j] == 0:
                continue
            union(i, j)
            
    # 최상위 부모 노드로 마지막에 한 번에 초기화
    for i in range(n):
        tmp = find(i)
        root[i] = tmp
    return len(set(root))

 

새로운 나의 풀이

• union-find 할 필요없이 그냥 bfs
• 대신 lst에 양방향으로 다 넣어줘야함
  • 처음에 i번째 컴퓨터는 i 이상의 연결된값만 단방향으로 넣어줬더니 예외발생
  • 0-2-1 로 연결된경우 1→2 는 연결해뒀는데 2→1 은 안해놔서 0→2 후에 2→1로 가지못해서 틀림

from collections import deque

def solution(n, computers):
    answer = 0
    n=len(computers)
    
    lst=[]
    for i in range(n):
        tmp=[]
        for j in range(n):
            if computers[i][j]==1:
                tmp.append(j)
        lst.append(tmp)
        
    def bfs(k):
        queue=deque([k])
        visited[k]=True
        
        while queue:
            cur=queue.popleft()
            for nxt in lst[cur]:
                if visited[nxt]:
                    continue
                visited[nxt]=True
                queue.append(nxt)
    
    visited=[False for _ in range(n)]
    for i in range(n):
        if not visited[i]:
            answer+=1
            bfs(i)
            
    return answer