[Python] 파이썬 프로그래머스 네트워크

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

프로그래머스

---

나의 풀이

네트워크는 아래의 리스트에 맞게 연결되어 있고 연결된 네트워크는 같은 네트워크 상에 존재한다.

컴퓨터 개수가 n, 연결에 대한 정보가 담긴 2차원 배열이 있다고 할 때 네트워크 개수를 구하라.

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

1번째 네트워크 구조

2번째 네트워크 구조

---

• for문을 통해 Check가 False일 때 해당 네트워크를 탐색함
• 위의 네트워크 탐색 중 연결된 네트워크가 다른 연결을 가지고 있으면 해당 인덱스의 네트워크도 탐색함

---

def DFS(idx, computers, check):
    for i, c in enumerate(computers[idx]):
        if check[i] == False and c == 1:
            check[i] = True
            DFS(i, computers, check)

def solution(n, computers):
    check = [False] * n
    answer = 0
    for i in range(n):
        if check[i] == False:
            answer += 1
            DFS(i, computers, check)

    return answer

---

다른 사람의 풀이

tree 탐색을 DFS로 했던 위와는 다르게 1이 들어있는 idx를 stack에 넣어 탐색하였다.

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(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