[프로그래머스] 네트워크

문제

• 네트워크의 개수 구하기
• 컴퓨터 A에서 B로 연결된다면, 같은 네트워크 상에 있다고 할 수 있다.
  • 1 <= 컴퓨터 개수 n <= 200

 

풀이 1

• 몇 개의 연결 그래프가 있는지 세는 문제
• 시간 복잡도 : union/find 연산 횟수는 정확히 모르지만 충분히 가능할 것으로 보임
  • v=1000, 연산횟수 100만 번일때, 약 1000만 번의 연산 필요!
• 유니온 파인드로 연결 그래프끼리 묶어버리고,
• parent 에서 몇 개 루트 노드가 있는지 카운팅 하기

 

# 부모 찾기
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

# 합치기
def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
def solution(n, computers):
    parent = [i for i in range(n)]
    for i, info in enumerate(computers):
        for j, link in enumerate(info):
            if link and parent[i] != parent[j] :	# 연결되어 있는데, 부모가 다른 경우
                union(parent, parent[i], parent[j])	# 합치기
    
    # 루트 노드 개수 세기
    answer = 0
    for i in range(n):
        if i == find(parent, i):
            answer += 1
    return answer

 

 

 

풀이 2

• 생각해보니 DFS/BFS 카테고리 문제니까 해당 알고리즘으로 풀어보기
• 첫 루트 노드에서 시작해, 연결된 부분을 모두 방문처리하기
• 루트 노드가 몇 개인지 카운트하기

 

from collections import deque

# 연결된 노드 방문처리하기
def bfs(graph, visited, start):
    q = deque([start])
    visited[start] = True
    while q:
        now = q.popleft()
        
        # 루트 노드에서 연결된 노드 찾기
        for i, link in enumerate(graph[start]) :
            if link and not visited[i] :
                visited[i] = True
                bfs(graph, visited, i)	# 연결된 노드 방문처리
            
def solution(n, computers):
    answer = 0
    visited = [False]*n
    for i in range(n):
        if not visited[i] :		# 루트 노드가 될 수 있으면
            bfs(computers, visited, i)
            answer += 1			# 정답 +1
            
    return answer

 

References

• 프로그래머스 고득점 Kit BFS/DFS