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

 

 

나의 풀이

def solution(n, computers):

    network = [i for i in range(n)]

    for i, c in enumerate(computers):
        for j in range(n):
            if i != j and c[j] and network[i] != network[j]:
                small, large = min(network[i], network[j]), max(network[i], network[j])
                for k in range(n):
                    if network[k] == large:
                        network[k] = small

    return len(set(network))

 - min과 max 불필요 : 같기만 하면 문제 없음

 

 

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

 

 

 

BFS를 활용한 풀이

def solution(n, computers):    
    def BFS(node, visit):
        que = [node]
        visit[node] = 1
        while que:
            v = que.pop(0)
            for i in range(n):
                if computers[v][i] == 1 and visit[i] == 0:
                    visit[i] = 1
                    que.append(i)
        return visit
    visit = [0 for i in range(n)]
    answer = 0
    for i in range(n):
        try:
            visit = BFS(visit.index(0), visit)
            answer += 1
        except:
            break
    return answer