[프로그래머스][LV.3] 네트워크 | python3

문제링크:  네트워크

---

문제설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

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

 

제한조건

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

---

 

문제풀이

def solution(n, computers):
    answer = 0
    c=[i for i in range(n)]
    connect=set()
    # 인덱스가 연결된 컴퓨터 숫자들... 이미 줬으니까 이걸 이용하여 풀 수 있을 거 같은데
    for i in range(n):
        for j in range(n):
            if computers[i][j]==1 and (i,j) not in connect and (j,i) not in connect:
                if c[i]==c[j]: continue
                c[j]=i
                connect.add((i,j))
                connect.add((j,i))
                
    
    answer=len(set(c))
            
    return answer

 

여기서 어제 풀었던 섬 연결하기 코드를 참고하면서 풀어봤는데 답이 안나온다.

 

def solution(n, computers):
    answer = 0
    c=[i for i in range(n)]
    # connect=set()
    # 인덱스가 연결된 컴퓨터 숫자들... 이미 줬으니까 이걸 이용하여 풀 수 있을 거 같은데
    # 연결된 값들을 옮김... 그래서 간접적으로 연결된 것들도 같은 곳에 있다는 걸 표시해야함.
    connect=[[i] for i in range(n)]
    for i in range(0,n//2):
        for j in range(n//2,n):
            if computers[i][j]==1:
                i=c[i]
                j=c[j]
                if i==j: continue
                c[j]=i
                while connect[j]:
                    q=connect[j].pop()
                    connect[i].append(q)
                
    
    answer=len(set(c))
            
    return answer

 

직접 연결뿐만 아니라 간접 연결까지 반영하기 위해 for k in range(n)이 필요함

 

나의코드

def solution(n, computers):
    answer = 0
    c=[i for i in range(n)] # 각 노드의 대표값 저장
    # connect=set()
    # 인덱스가 연결된 컴퓨터 숫자들... 이미 줬으니까 이걸 이용하여 풀 수 있을 거 같은데
    # 연결된 값들을 옮김... 그래서 간접적으로 연결된 것들도 같은 곳에 있다는 걸 표시해야함.
    connect=[[i] for i in range(n)] # 연결된 노드 리스트
    for i in range(n):
        for j in range(n):
            if computers[i][j]==1 and c[i] != c[j]: # 대표값이 다르면
                old,new=c[j],c[i] # old: 변경될 값, new: 유지될 값
                
                for k in range(n): # 전체 배열을 돌면서 old 값을 new로 변경
                    if c[k]==old:
                        c[k]=new
                
    
    answer=len(set(c))
            
    return answer

 

---

 

참고하기

def solution(n, computers):
    visited = [False] * n  # 방문 여부 체크
    def dfs(node):
        for i in range(n):
            if computers[node][i] == 1 and not visited[i]:  # 연결되어 있고 방문 안 했으면
                visited[i] = True
                dfs(i)
    
    answer = 0
    for i in range(n):
        if not visited[i]:  # 새로운 네트워크 시작점 발견
            visited[i] = True
            dfs(i)
            answer += 1  # 새로운 네트워크 개수 증가
    
    return answer

DFS 활용..

재귀를 이용한 풀이인데...나는 재귀는 좀 어렵다..ㅠㅜ

 

def solution(n, computers):
    answer = 0
    visited = [0 for i in range(n)]
    def dfs(computers, visited, start):
        stack = [start]
        while stack:
            j = stack.pop()
            if visited[j] == 0:
                visited[j] = 1
            # for i in range(len(computers)-1, -1, -1):
            for i in range(0, len(computers)):
                if computers[j][i] ==1 and visited[i] == 0:
                    stack.append(i)
    i=0
    while 0 in visited:
        if visited[i] ==0:
            dfs(computers, visited, i)
            answer +=1
        i+=1
    return answer

연결된 것들을 다 돌면 dfs함수를 나오면서 answer에 1이 추가