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

문제

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

프로그래머스

---

아이디어

DFS로 풀 수 있다. 우선 방문 여부를 나타내는 리스트를 생성한다. (처음에는 모두 False)

그리고 각 컴퓨터에 대해서 dfs를 수행한다. 

 

이 때, dfs 알고리즘를 구성하기 위한 변수는 다음과 같다. 

- 전체 컴퓨터 수 n

- 컴퓨터 간의 연결 여부를 나타내는 리스트 computers

- 각 컴퓨터의 방문 여부 visited

- 현재 탐색을 진행할 컴퓨터 start

 

먼저 탐색할 컴퓨터는 현재 방문한 상태이기 때문에 방문 여부를 True로 바꾼다. 

이 때, n개의 컴퓨터와 연결 여부를 탐색해야 한다. 이 때, 두 가지를 확인해야 한다.

- 방문 여부가 False (이미 방문을 했다면 다른 네트워크에 count되었기 때문에 제외)

- 현재 탐색 중인 컴퓨터와 연결되어 있어야 한다.

만약 2가지 조건을 만족한다면, 방문한 컴퓨터에 대해서도 또 다시 같은 과정을 반복한다. 그리고 탐색이 끝나게 되면 하나의 네트워크가 형성된 것이다.

---

Solution

def dfs(n, computers, visited, start) :
    visited[start] = True 
    
    for i in range(n) : 
        if visited[i] == False and computers[start][i] == 1 : 
            visited = dfs(n, computers, visited, i)
            
    return visited

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    for start in range(n) : 
        if visited[start] == False : 
            dfs(n, computers, visited, start) 
            answer += 1
    return answer