네트워크

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

 

def DFS(curVertex,depth):
    if depth == n:
        return

    visited[curVertex] = True

    for nextVertex in range(n):
        if visited[nextVertex] == True:
            continue
        if curVertex == nextVertex:
            continue
        if computers[curVertex][nextVertex] == 1:
            DFS(nextVertex,depth+1)


answer = 0

for vertex in range(n):
    if visited[vertex] == False:
        answer +=1
        DFS(vertex,0)

return answerit 취업을 위한 알고리즘 문제 풀이

문제

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

[

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

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있

programmers.co.kr

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

코드

# https://programmers.co.kr/learn/courses/30/lessons/43162
def solution(n, computers):
    visited = [False]*n

    def DFS(curVertex,depth):
        if depth == n:
            return

        visited[curVertex] = True

        for nextVertex in range(n):
            if visited[nextVertex] == True:
                continue
            if curVertex == nextVertex:
                continue
            if computers[curVertex][nextVertex] == 1:
                DFS(nextVertex,depth+1)


    answer = 0

    for vertex in range(n):
        if visited[vertex] == False:
            answer +=1
            DFS(vertex,0)

    return answer

문제해결방법

• 1번부터 n 까지 루트로 DFS를 탐색한다.
  • 이때 이미 체크한 컴퓨터는 루트로 시작할 수 없다.
• DFS 탐색을하면서 끊어진 네트워크가 나오면 return 한다.
• 루트가 될 수 있는 컴퓨터의 개수가 네트워크의 개수로 하여 answer를 반환한다.
• 그래프 연결상태

• 그래프 연결상태 인접행렬 방식으로 표현

연결된 노드끼리 1로 표시하였다. 또, 표에서 대각선은 자기 자신을 가리키는데 자기자신끼리도 연결된 상태로 보고 1로표시 하였다. 하지만 DFS탐색에서 현재 노드에서 연결된 노드로 이동할때 자기 자신은 제외해줄 것이다.

• DFS 탐색 과정

vertex 방문 처리

0번 vertex와 연결되었고 방문하지 않은 1번 vertex 탐색

1번 vertex 방문 처리

• 1번과 연결되었고 방문되지 않은 노드가 더이상 없으므로 return

• 0번과 연결되었고 방문되지 않은 노드가 더이상 없으므로 return

• Main의 for문에서 다음 차례인 1번 vertex 는 0번 vertex에서 시작해 네트워크 형성여부를 체크했으므로 다음 vertex 2번 시작

• 2번 방문 체크

• 2번 vertex와 연결된 노드가 더이상 없으므로 return

• 색칠된 개수가 네트워크 개수(노랑,초록) 2개의 네트워크로 구성