프로그래머스 - 네트워크 [파이썬]

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

---

풀이 과정

정점에 해당하는 n, 간선에 해당하는 computers를 줄테니 그래프의 연결 요소에 해당하는 네트워크의 개수를 구하라는 문제이다.

 

즉 그래프의 정보를 줄테니 모든 연결 요소의 개수를 구하라는 소리고, 연결 요소의 개수를 구하는 방법은 모든 정점을 살펴보면서 이미 방문한 정점이면 넘어가고, 방문하지 않은 정점이면 해당 정점에 대해 dfs (혹은 bfs) 탐색을 시행해 해당 정점, 연결된 정점들을 전부 다 방문한 정점으로 바꿔주고 연결 요소의 개수를 하나 늘려주면 된다.

 

인접 배열, 인접 리스트, 간선 리스트등으로 그래프의 연결 상태를 표현할 수 있고 이 문제에서는 인접 배열로 주어짐을 고려하면서 문제를 해결하였다.

---

소스 코드

def dfs(x, n, computers, check):
    check[x] = True
    for i in range(n):
        if computers[x][i] and not check[i]:
            dfs(i, n, computers, check)


def solution(n, computers):
    answer = 0
    check = [False for _ in range(n)]

    for i in range(n):
        if not check[i]:
            answer += 1
            dfs(i, n, computers, check)

    return answer