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

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

프로그래머스

 

• 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미
• 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있음
• 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있음
• 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return

제한사항

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

 

"""
입출력 예시)

n = 3, computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]] -> 2
n = 3, computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]] -> 1
"""

 

# n = 3, computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]] -> 2

 

• 1번 컴퓨터와 2번 컴퓨터 연결
• => 1, 2번 컴퓨터는 같은 네트워크 상에 있고, 3번 컴퓨터는 연결되어 있지 않기 때문에 네트워크의 개수는 2

 

# n = 3, computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]] -> 1

 

• 1번 컴퓨터와 2번 컴퓨터 연결
• 2번 컴퓨터와 3번 컴퓨터 연결
  • -> 1번 컴퓨터와 3번 컴퓨터도 간접적으로 연결
• => 1, 2, 3번 컴퓨터가 모두 같은 네트워크 상에 있기 때문에 네트워크의 개수는 1

 

 

## 의사코드 ##

# 연결 요소 개수 세기 -> DFS

# 간접적으로 연결되어 있다면 하나의 네트워크로 판단
# 다른 컴퓨터와 연결되지 않은 독립적인 컴퓨터도 하나의 네트워크로 판단

# dfs 수행한 다음 네트워크 + 1

 

 

 

통과한 코드

 

def solution(n, computers):

    # DFS
    def dfs(node):
        # 현재 노드 방문처리 
        visited[node] = True
        # 인접노드 탐색 
        for j in range(n):
            # 아직 방문하지 않았으면서 연결되어 있는 컴퓨터라면 DFS 수행
            if not visited[j] and computers[node][j] == 1:
                dfs(j)
    
    answer = 0 # 네트워크 개수 
    visited = [False] * n 
    for i in range(n):
        # 아직 방문하지 않았으면 DFS 수행
        if not visited[i]:
            dfs(i)
            # DFS 탐색이 끝난 후 + 1
            answer += 1

    return answer

 

 

-> DFS로 구현

 

 

• 과정 확인 

n = 3
computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

"""
i: 0
i의 방문처리 여부(visited[i]): False 

<아직 방문하지 않았으면 DFS 수행>
# 인접노드 탐색 #
j: 0
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

# 인접노드 탐색 #
j: 1
j의 방문처리 여부(visited[j]): False
연결 정보(computers[node][j]): 1 

[아직 방문하지 않았으면서 연결되어 있는 컴퓨터라면 DFS 수행]
# 인접노드 탐색 #
j: 0
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

# 인접노드 탐색 #
j: 1
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

# 인접노드 탐색 #
j: 2
j의 방문처리 여부(visited[j]): False
연결 정보(computers[node][j]): 1 

[아직 방문하지 않았으면서 연결되어 있는 컴퓨터라면 DFS 수행]
# 인접노드 탐색 #
j: 0
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 0 

# 인접노드 탐색 #
j: 1
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

# 인접노드 탐색 #
j: 2
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 
# 인접노드 탐색 #
j: 2
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 0 

네트워크 개수: 1
----------------------------------------------------------------------
i: 1
i의 방문처리 여부(visited[i]): True 

i: 2
i의 방문처리 여부(visited[i]): True 

1
"""

 

 

n = 3
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

"""
i: 0
i의 방문처리 여부(visited[i]): False 

<아직 방문하지 않았으면 DFS 수행>
# 인접노드 탐색 #
j: 0
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

# 인접노드 탐색 #
j: 1
j의 방문처리 여부(visited[j]): False
연결 정보(computers[node][j]): 1 

[아직 방문하지 않았으면서 연결되어 있는 컴퓨터라면 DFS 수행]
# 인접노드 탐색 #
j: 0
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

# 인접노드 탐색 #
j: 1
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

# 인접노드 탐색 #
j: 2
j의 방문처리 여부(visited[j]): False
연결 정보(computers[node][j]): 0 

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 
# 인접노드 탐색 #
j: 2
j의 방문처리 여부(visited[j]): False
연결 정보(computers[node][j]): 0 

네트워크 개수: 1
----------------------------------------------------------------------
i: 1
i의 방문처리 여부(visited[i]): True 

i: 2
i의 방문처리 여부(visited[i]): False 

<아직 방문하지 않았으면 DFS 수행>
# 인접노드 탐색 #
j: 0
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 0 

# 인접노드 탐색 #
j: 1
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 0 

# 인접노드 탐색 #
j: 2
j의 방문처리 여부(visited[j]): True
연결 정보(computers[node][j]): 1 

네트워크 개수: 2
----------------------------------------------------------------------

2
"""

 

 

 

다른 풀이

 

from collections import deque

def solution(n, computers):            
    
    def BFS(i):
        q = deque()
        q.append(i)
        while q:
            i = q.popleft()
            visited[i] = 1
            for a in range(n):
                if computers[i][a] and not visited[a]:
                     q.append(a)
                
    answer = 0
    visited = [0 for i in range(len(computers))]
    for i in range(n):
        if not visited[i]:
            BFS(i)
            answer += 1
        
    return answer

 

 

-> BFS로 구현

 

 

 

 

참고)

 

https://daeun-computer-uneasy.tistory.com/70

[프로그래머스] 네트워크 (python) - BFS/DFS

 

https://velog.io/@op032/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-python

프로그래머스 네트워크 (python)