[Programmers 알고리즘 고득점 Kit] 네트워크 [Python]

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3

프로그래머스

 

 

---

풀이

그래프의 간선이 2차원 배열로 주어졌을 때, 독립된 정점 그룹의 수를 세는 문제다.

정점의 수는 최대 200이므로 완전 탐색을 하기에 시간이 충분하다.

BFS를 하며 연결된 정점들을 전부 탐색 후 그룹의 수를 증가시키는 방식으로 해결했다.

def solution(n, computers):
    visited = [False] * n
    cnt = 0
    for i in range(n):
        if not visited[i]:
            bfs(i, visited, computers, n)
            cnt += 1
    return cnt;

computers 에는 자기 자신에 대한 간선 정보도 포함되어 있으니 탐색 시 이를 제외한 다른 정점으로 탐색해야 한다.

def bfs(start, visited, computers, n):
    queue = deque([start])
    visited[start] = True
    while queue:
        cur = queue.popleft()
        for i in range(n):
            if not visited[i] and computers[cur][i] == 1 and cur != i:
                visited[i] = True
                queue.append(i)

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/Programmers/Coding%20Test%20High%20Score%20Kit/DFS%2BBFS/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC.py