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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

컴퓨터들을 연결하여 네트워크가 만들어지고, 서로 다른 네트워크가 몇개인지 확인이 필요하므로 서로소 집합 알고리즘을 이용하여 네트워크 개수를 확인하였습니다.

2) 알고리즘

• 서로소 집합

3) 풀이 코드

사용 언어 - Python

def solution(n, computers):
    network = list(range(n))                # 컴퓨터들 서로간 연결 정보

    def union(x, y):                        # 컴퓨터 두대 연결
        network[find(y)] = find(x)          # 각 연결된 컴퓨터의 대표 컴퓨터를 연결
    
    def find(x):                            # 해당 컴퓨터 네트워크의 대표 컴퓨터 검색
        if x != network[x]:                 # 현재 컴퓨터가 대표 컴퓨터가 아니라면
            network[x] = find(network[x])   # 대표 컴퓨터를 찾음
        return network[x]
    
    for i in range(n):                      # 컴퓨터들 연결 정보 반복
        for j in range(i+1, n):
            if computers[i][j]:             # i와 j가 연결되어 있다면
                union(i, j)                 # i와 j 연결 시키기
                
    for i in range(n):                      # 모든 컴퓨터들 네트워크의 대표 컴퓨터로 연결관계 정리
        find(i)    
    
    return len(set(network))                # 네트워크 개수 카운트

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

코딩테스트 연습 - 네트워크

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다