[level 3] 네트워크

 

1. 문제 

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

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

---

 

2. 문제 풀이 

 

문제 풀이 접근법1

1) 노드의 수 만큼 visited 리스트를 0으로 초기화한다. 

2) 노드의 개수만큼 for문을 수행한다. 만약 i번째 노드에 방문한 적이 없으면 dfs 함수를 호출한다. 

이때, dfs 함수에 [ 현재 컴퓨터의 번호, 방문 여부 체크 리스트, computers 리스트 ] 를 함께 전달한다. 

3) dfs 함수에서 현재 노드의 visited 여부를 1로 변경한다. 

4) computers의 길이 만큼(= 노드의 수 만큼) 반복문을 진행한다. 

*모든 노드를 탐색 하기 위함 → 모든 노드가 현재 노드와 연결 되어 있는 지를 탐색하기 위함 

5) 만약 j번째 노드가 탐색 되지 않았고, computers[i][j] == 1로 i번째 컴퓨터와 j번째 컴퓨터가 서로 연결되어 있다면 dfs함수를 다시 호출한다.  → 연결된 컴퓨터와 더 연결된 컴퓨터가 있는 지를 확인하기 위함 

(A와 연결된 B 와 연결된 C = A와 C도 연결된 것이므로 하나의 네트워크임) 

6) 연결된 컴퓨터가 더 없을 경우, 다시 반환이 된다(dfs 재귀가 더 이상 이루어지지 않음) 

7) 하나의 network를 찾은 것이므로 answer에 +1 진행

8) 그 외에 방문하지 않은 노드를 탐색한다. 

def dfs(node, visited, computers):
    visited[node] = 1
    
    for i in range(len(computers)):
        if not visited[i] and computers[node][i]==1:
            dfs(i, visited, computers)


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

    return answer

 

 

 

---

 

아 answer+=1되는거 너무 이해 안돼서 예시 테스트 케이스 1번가지고 챗gpt랑 열.대(열정 대화)한 사진.. 

 

dfs 너무 어려워요

그러니까 문제 많이 풀어보자... ^_^