네트워크 - UnionFind / BFS

 

DFS/ BFS 문제로 분류가 되어있었지만, 내가 알고리즘 책에서 본 Union-Find가 가장 먼저 생각나는 문제였다.

따라서 Union-Find를 구현해서 풀어보기로 하였다.

 

풀이방법

1. 인접행렬은 대칭이므로 반만 써서 모든 노드를 방문한다.
2. su 리스트는 연결되어 있는 노드의 가장 부모 노드를 나타낸다.
3. 예를 들어 1,2,3,4가 서로 연결되어 있고, 부모노드가 1이라면 1,1,1,1이라고 써진다.
4. 부모노드가 자신이 될 때까지 while문을 이용해서 계속 temp = su[temp]를 한다.
5. 만약 같아진다면, su[i]와 같은 부모노드를 가지고 있는 노드를 모두 temp로 바꾼다.

 

소스코드 - UnionFind

def solution(n, computers):
    su = [x for x in range(0,n)]
    answer = 0
    for i in range(n):
        for j in range(i):
        
            if computers[i][j] == 1: #i,j 노드가 연결되어 있는 경우
                temp = j
                
                while True:
                    if su[temp] == temp: #부모노드가 자기노드일 경우
                        for k in range(n):#i노드와 부모노드가 같은 노드들을 변환
                            if su[k] == su[i]:
                                su[k] = temp
                        break
                    else:
                        temp = su[temp] #부모노드를 찾기 위해 상위노드 대입
                        
                        
    #print(su)
    result = set(su) #노드 구분하기 위해 집합에 넣어서 노드 개수 구함
    answer = len(result)
    return answer

 

 

BFS로 푼 방법도 있었다.

 

풀이방법

1. visited라는 리스트로 노드를 방문했는지 여부를 확인한다.
2. 방문하지 않은 노드를 방문하여 BFS로 인접한 노드를 모두 방문한다. (answer +=1)
3. 2번을 반복하여 모든 노드를 방문할 때까지 수행한다.
4. 하나의 네트워크당 한번의 BFS가 시작되므로 BFS가 시작되는 횟수마다 네트워크 갯수가 증가한다.

소스코드 - BFS

def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            for i in range(0, len(computers)):
                if computers[j][i] ==1 and visited[i] == 0:
                    stack.append(i)
    i=0
    while 0 in visited:
        if visited[i] ==0:
            dfs(computers, visited, i)
            answer +=1
        i+=1
    return answer


출처: https://geonlee.tistory.com/54 [빠리의 택시 운전사]