(파이썬) [알고리즘 문제 풀이] - 네트워크 (프로그래머스)

오늘은 프로그래머스에서 레벨3 네트워크를 풀어 보았습니다.

컴퓨터의 개수와 연결에 대한 정보가 담긴 배열이 주어집니다.

서로 연결되어 있는 컴퓨터들의 모임을 네트워크라고 부르는데

과연 주어진 연결에서 네트워크가 몇개나 있는 찾아야 되는 문제 입니다.

문제를 풀기 위해 필요하다고 생각되는 것들을 적어 보았습니다.

• 컴퓨터 간의 연결을 저장해두는 자료구조가 필요
• 각 컴퓨터 마다 어떤 컴퓨터와 연결 되어 있는지 체크

연결들을 저장해두는 자료구조로 dictionary를 썼습니다.

각 컴퓨터가 key가 되며 해당 컴퓨터에 연결된 컴퓨터들의 집합은

value가 됩니다. 

저는 이 연결된 컴퓨터들의 집합을 set에 담았습니다.

예시) n = 3, computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

2번 컴퓨터와 연결된 다른 컴퓨터는 없기 때문에 value가 빈 set이 됩니다.

여기까지 되었으면 이제 본격적으로 컴퓨터 마다 연결되어 있는 컴퓨터들을 확인하겠습니다.

아직 확인 안한 컴퓨터를 담아두는 set과 

확인 작업이 필요한 컴퓨터를 넣어두는 리스트를 한개 만듭니다.

확인 작업이 필요한 리스트가 비었음으로 

0번 컴퓨터를 넣어 두겠습니다.

0번 컴퓨터와 연결된 컴퓨터를 확인해보니 오직 1번 컴퓨터하고만 연결 되어 있습니다.

1번 컴퓨터와 연결된 다른 컴퓨터는 0번 컴퓨터와 같은 네트워크이기 때문에

1번 컴퓨터도 확인 작업이 필요한 리스트 넣도록 하겠습니다.

0번 컴퓨터는 확인 작업이 끝났음으로 빼내었습니다.

1번 컴퓨터와 연결된 컴퓨터들을 확인해본 결과 

0번 컴퓨터하고만 연결되어 있었고 

0번 컴퓨터는 이미 확인 작업이 끝난 컴퓨터라 1번 컴퓨터의 확인 작업을 마치며

동시에 1개의 네트워크를 기록해둡니다. 

2번 컴퓨터는 확인결과 연결된 컴퓨터가 없음으로 

2번 컴퓨터만 포함된 1개의 네트워크가 추가 되며

알고리즘은 끝이 납니다.

def solution(n, computers):
    graph = {n:set() for n in range(len(computers))}
    for i in range(len(computers)):
        for j in range(len(computers)):
            if computers[i][j] == 1 and i != j:
                graph[i].add(j)
                graph[j].add(i)
                
    undiscovered = {n for n in graph}
    frontier = []
    answer = 0
    
    while len(undiscovered) or len(frontier):
        if not len(frontier):
            answer += 1
            frontier.append(undiscovered.pop())
            
        node = frontier.pop()
        for c in graph[node]:
            if c in undiscovered:
                frontier.append(c)
                undiscovered.remove(c)

    return answer