Programmers / 네트워크 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 네트워크 (3단계) DFS

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.

입출력 예ncomputersreturn

3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

---

나의 풀이

네트워크마다 연결 되어있는 노드가 다를 것이라고 예상되어 일단 각 노드에 연결된 다른 노드들을 딕셔너리 형태로 만들어주었다.

re.finditer('1',tmp) 는 tmp 문자열 안에 1이라는 문자가 몇번째 인덱스에 있는지 모두 반환한다!

꽤나 유용해서 다음번에도 많이 쓸 거 같다 생각보다 코테에 re 정규식이 엄청나게 도움되는듯

 

computers = [[1, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 1],[0, 0, 1, 1]] 라는 입력이 있다고 가정하면 해당 노드를 그림으로 나타내면 다음과 같다

이렇게 노드가 따로 연결되어있어 한번만 DFS 를 실행시키면 안된다

 

따라서 해당 그림(리스트) 딕셔너리로 변환하여 코드로 나타내면 다음과 같다

 

0번째 노드는 1번과 연결되어있음

1번째 노드는 0번과 연결되어있음

2번째 노드는 3번과 연결되어있음

3번째 노드는 2번과 연결되어있음

 

그리고 해당 구조를 DFS 로 구현해주었다

while stack:
    node = stack.pop()
    if node not in visited: # 방문한 노드가 아니라면
        visited.append(node)
        stack.extend(compute_dict[node])

전체 코드

import re
def solution(n, computers):
    network_line = []
    compute_index = [i for i in range(n)]
    compute_dict = {i:[] for i in range(n)}
    
    for i in range(n) :
        if 0 not in computers[i]:
            return 1
        other_net = computers[i][:i] + computers[i][i+1:] # i,i 번째 빼고 출력
        tmp = ''
        for j in computers[i]:
            tmp += str(j)
        if 1 in other_net:
            indices = [i.start() for i in re.finditer('1', tmp)] # 1의 인덱스를 반환함
            for indice in indices:
                if indice != i:
                    compute_dict[i].append(indice) # 딕셔너리 생성
    pos = 0
    while compute_index:
        if pos in compute_index:
            visited_list = DFS(pos,compute_dict)
            network_line.append(visited_list)
            compute_index = list(set(compute_index) - set(visited_list))
        pos += 1
    return len(network_line)

def DFS(pos,compute_dict):
    visited = list()
    stack = list()
    stack.append(pos)
    
    while stack:
        node = stack.pop()
        if node not in visited: # 방문한 노드가 아니라면
            visited.append(node)
            stack.extend(compute_dict[node])
    return visited

다른 풀이

(2024-4-24)

BFS 풀이

# BFS 풀이
from collections import deque

def solution(n, computers):
    answer = 0
    visited = [0 for _ in range(n)]
    
    def BFS(start,visited,computers):
        queue = deque([start])
        while queue:
            q = queue.popleft()
            for i in range(n):
                if computers[q][i] == 1 and visited[i] == 0:
                    queue.append(i)
                    visited[i] = 1
                    
    for i in range(n):
        if visited[i] == 0:
            BFS(i,visited,computers)
            answer += 1   
    return answer

 

DFS풀이

# DFS 풀이

def solution(n, computers):
    answer = 0
    visited = [0 for _ in range(n)]
    def DFS(start,computers,visited):
        for i in range(n):
            if computers[start][i] == 1 and visited[i] == 0:
                visited[i] = 1
                DFS(i,computers,visited)
            
    for i in range(n):
        if visited[i] == 0:
            DFS(i,computers,visited)
            answer += 1
    return answer

---

※ 알아야 할 것

- re.finditer('1',tmp) 는 tmp 문자열 안에 1이라는 문자가 몇번째 인덱스에 있는지 모두 반환