프로그래머스(Programmers) : 네트워크 - python 풀이

🔴 문제 요약

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

‼ 제한 사항

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

🟠 접근 방법 1 : 인접 행렬 재구성

• 그래프 탐색 문제로 보이고 n도 200 이하이므로, 보통의 그래프 탐색 알고리즘(BFS, DFS)을 적용해도 될 것이다.
• 결국 전체 네트워크가 몇 덩어리로 나뉘어져 있는지를 알면 되므로, BFS를 적용해 탐색이 몇 번 일어나는지 확인하면 된다.
• 다만, 주어진 인접행렬은 현재 두 컴퓨터가 연결되었다는 정보를 나타내므로, BFS탐색을 용이하게 하기 위해 각 컴퓨터가 연결 중인 다른 컴퓨터의 리스트를 따로 관리할 필요가 있다.

🔠 접근 방법 1 - 해결 코드

from typing import List, Deque
from collections import deque, defaultdict

networks = defaultdict(list)
visited: List[bool] = list()

def bfs(init_computer:int):
    visited[init_computer] = True                    # 초기 컴퓨터 방문 처리
    queue: Deque[int] = deque([init_computer])

    while queue:
        cur_computer = queue.popleft()

        for computer in networks[cur_computer]:      # 현재 탐색 중인 컴퓨터와 연결된 컴퓨터들을 탐색
            if not visited[computer]:                   # 그 중 아직 방문되어있지 않은 컴퓨터들에 대해서만
                queue.append(computer)                  # 큐에 넣고 탐색
                visited[computer] = True

    return 1                                        # 정상 탐색 완료시 1 반환


def solution(n: int, computers: List[List[int]]) -> int:
    '''
    컴퓨터가 연결되어있다는 정보를 나타내는 인접 행렬을 특정 컴퓨터에 대한 연결 컴퓨터들을 담은 dict로 변환한 풀이
    '''

    global networks, visited
    num_of_networks: int = 0
    visited = [False for _ in range(n)]     # 컴퓨터들의 탐색 여부 관리

    for r in range(n):                      # dict: {컴퓨터 : [연결된 컴퓨터 들]} 로 관리
        for c in range(n):
            if computers[r][c]:
                networks[r].append(c)       # 양방향 연결되어있음에 주의해야 함
                networks[c].append(r)

    for computer in range(n):               
        if not visited[computer]:
            num_of_networks += bfs(computer)  # 정상적인 탐색이 한 번 끝나면 하나의 네트워크가 형성되어 있다는 것임

    return num_of_networks

🟡 접근 방법 2 : 인접 행렬 그대로 활용

• 풀이하다 보니 인접 행렬을 재구성 하는 과정 없이 풀이가 가능할 것 같다. 탐색 인덱스를 적절히 활용하면 될 것 같다.

🔠 접근 방법 2 - 해결 코드

from typing import List, Deque
from collections import deque, defaultdict

visited: List[bool] = list()

def bfs_adjMatrix(init_computer: int, computers: List[List[int]]) -> int:
    global visited

    queue = deque([init_computer])
    visited[init_computer] = True

    while queue:
        cur_computer = queue.popleft()       
        for nxt_computer, is_connect in enumerate(computers[cur_computer]):   # 현재 탐색 중인 컴퓨터의 연결 정보 순회
            if is_connect and not visited[nxt_computer]:                       # 연결되어있고 아직 방문되지 않은 컴퓨터만 탐색
                queue.append(nxt_computer)
                visited[nxt_computer] = True           
    return 1

def solution_adjMatrix(n: int, computers: List[List[int]]) -> int:
    '''
    주어진 인접 행렬을 그대로 활용한 풀이
    '''
    global visited
    num_of_networks: int = 0
    visited = [False for _ in range(n)]

    for computer in range(n):
        if not visited[computer]:
            num_of_networks += bfs_adjMatrix(computer,computers)

    return num_of_networks

🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!

✏️ Algorithm Study

본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.