[코딩테스트/프로그래머스/Python]네트워크

💡생각

1. deque 사용.
2. deque에 먼저 0을 넣음.
3. for문을 돌면서 deque에 computers[i]에서 1인것들을 넣음.
4. 그리고 deque에서 i를 빼면서 computers[i]를 다 0으로 만듦.
5. deque에서 1개를 뺀 다음 거기에 해당하는 숫자에 대해 위에 계산을 반복함.
6. deque에 아무것도 없으면 answer에 1더함.
7. 배열에서 아직 1이 남아있는지 확인하고 있으면 그 숫자부터 다시 위에 계산을 반복함.
8. 배열의 원소가 모두 0이 되면 answer return함.

❓잘못된 코드1

테스트 케이스는 통과했지만 채점을 통과하지 못함.

문제점1. deq안에 중복된 숫자가 들어감.

from collections import deque

def solution(n, computers):
    answer = 0
    net = 0
    popnum = 0
    com_cnt = [1 for i in range(n)]
    deq = deque()
    while 1 in com_cnt:
        if com_cnt[popnum] == 1:
            net = popnum
        else:
            net = com_cnt.index(1)
        com_cnt[net] = 0
        for j in range(0, n):
            if computers[net][j] == 1 and com_cnt[j] == 1:
                deq.append(j)
            computers[net][j] = 0
        if deq:
            popnum = deq.popleft()     
        else:
            answer += 1
        
    return answer

❗해결: deq안에 넣을 때 중복체크를 해준 다음에 넣어줌.

💡테스트 통과한 코드

n: 컴퓨터의 개수
computers: 연결에 대한 정보가 담긴 2차원 배열
answer: 네트워크 개수 세는 변수
net: 연결을 확인할 컴퓨터의 번호
popnum: deq에서 pop한 숫자
com_cnt: 연결을 확인한 컴퓨터를 확인해주는 배열(0:확인완료, 1:확인미완료)
deq: 확인하고 있는 컴퓨터와 연결된 컴퓨터의 번호를 담은 que

1. com_cnt배열의 요소가 다 0이 될때까지 while문을 돌림.(컴퓨터의 연결을 다 확인할 때까지)
2. 만약 deq에서 pop한 번호의 컴퓨터가 아직 연결을 확인하지 않았으면 확인할 컴퓨터의 번호인 net에 pop한 번호를 넣음.(처음에는 0이 들어감.)
3. 연결을 확인했다면 com_cnt 배열에 아직 확인안한 컴퓨터가 있는지 확인한 후 제일 앞에있는 인덱스의 컴퓨터를 net에 넣음.
4. 확인했다는 의미로 com_cnt배열에서 인덱스 net을 0으로 바꿈.
5. for문을 돌면서 만약 확인하고 있는 컴퓨터와 연결된 컴퓨터가 아직 확인하지 않은 컴퓨터이고 deq에 들어있지 않은 컴퓨터라면 deq에 append함.
6. 확인하고 있는 컴퓨터의 연결을 다 확인한 뒤 deq이 비어있지 않다면 pop해서 popnum에 저장하고 deq이 비었다면 answer에 +1을 함.
7. 모든 컴퓨터의 연결을 다 확인했다면 answer값을 return함.

from collections import deque

def solution(n, computers):
    answer = 0
    net = 0
    popnum = 0
    com_cnt = [1 for i in range(n)]
    deq = deque()
    while 1 in com_cnt:
        if com_cnt[popnum] == 1:
            net = popnum
        else:
            net = com_cnt.index(1)
        com_cnt[net] = 0
        for j in range(0, n):
            if computers[net][j] == 1 and com_cnt[j] == 1 and j not in deq:
                deq.append(j)
        if deq:
            popnum = deq.popleft()  
        else:
            answer += 1
        
    return answer

⏬다른사람의 코드

내 코드는 메모리도 차지를 많이하고 코드도 길어서 코드가 짧은 다른 사람의 코드를 찾아보았음.

---

🔗풀이 참고
프로그래머스-네트워크 다른사람의 풀이를 참고하였습니다.

def solution(n, computers):
    temp = []
    for i in range(n):
        temp.append(i)
    for i in range(n):
        for j in range(n):
            if computers[i][j]:
                for k in range(n):
                    if temp[k] == temp[i]:
                        temp[k] = temp[j]
    return len(set(temp))

플로이드-워셜 알고리즘을 사용했다고함.

1. temp배열을 만들어 모든 컴퓨터(n)을 append함.
2. 만약 컴퓨터i와 j가 연결되어있다면 temp배열의 i인덱스에 temp배열의 j인덱스에 해당하는 숫자를 넣어줌.
3. for문을 다 돌면 temp배열의 중복되는 숫자를 제외하고 그 길이를 return해줌. (temp배열에 중복된 숫자는 같은 네트워크를 사용하고 있다는걸 의미함.)

---

✅플로이드-워셜 알고리즘

• 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘.
• 플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용.
• 시간복잡도 = O(V^3)

🔗프로그래머스 - 네트워크
https://programmers.co.kr/learn/courses/30/lessons/43162