프로그래머스 Lv. 3 네트워크 Python

문제 링크

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

프로그래머스

정답 코드

from collections import deque
def solution(n, computers):
    answer = 0
    adjL = [[] for _ in range(n+1)]
    for i in range(n):
        for j in range(i, n):
            if i == j:
                continue
            if computers[i][j]:
                adjL[i+1].append(j+1)
                adjL[j+1].append(i+1)
                
    V = [0 for _ in range(n+1)]
    for start in range(1, n+1):
        if V[start]:
            continue
        V[start] = 1
        answer += 1
        q = deque()
        q.append(start)
        while q:
            current = q.popleft()
            for next in adjL[current]:
                if V[next]:
                    continue
                V[next] = 1
                q.append(next)   
    return answer

풀이 방법

- 인접 행렬(Adjacency Matrix) : adjM = [[1, 0, 0], [0, 1, 1], [1, 1, 1]]

- 인접 리스트(Adjacency List): adjL = [[], [2], [1], [1, 2, 3]] (맨 앞 0번 노드는 대부분 비어있음)

- 우선 인접 행렬보단 인접 리스트가 편해서 인접리스트로 바꿨다.

- 첫 번째 그림과 두 번째 그림을 보면 알 수 있듯이

    - 첫 번째 그림 설명

        - 1, 2가 연결되어 있으므로 네트워크 1개, 3은 하나만 연결 되어 있으므로 네트워크 2개이다.

    - 두 번째 그림 설명

        - 1, 2, 3이 모두 연결 되어 있으므로 네트워크 1개

첫 번째

 

두 번째

- 즉 연결된 것들이 몇 개 인지 세는 문제이다.

- 방문배열을 밖에 놔두고 반복문을 돌기 직전에 이미 방문 했는지 확인한다.

- 확인 결과 방문하지 않은 노드이면 네트워크 길이 + 1이다.

느낀점

- 오랜만에 인접 행렬, 인접 리스트에 대해서 공부해봤다.

- 의미는 잘 몰랐는데 이번에 제대로 고 넘어갈 수 있어서 좋았다.