네트워크

네트워크
깊이/너비 우선 탐색(DFS/BFS) 
5703명 완료

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

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

 

파이썬(python)

최적의 풀이는 아니지만 파이썬의 집합을 이용하면 쉽게 풀 수 있습니다. 
n개의 컴퓨터가 있으니, 각각의 컴퓨터와 연결된 컴퓨터의 목록을 담는 집합(네트워크)을 만들고
이 각각의 네트워크끼리의 교집합이 존재한다면 둘을 합집합으로 대체하는 방식으로
전수조사를 통해 네트워크를 찾아가는 방식입니다. 물론 비효율적입니다. 

def solution(n, computers):
    networks = [{i} for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if computers[i][j] == 1:
                networks[i].add(j)
                networks[j].add(i)
    for i in range(n):
        for j in range(n):
            if networks[i] & networks[j]:
                networks[i] = networks[j] = networks[i] | networks[j]
    return len(set(tuple(sorted(network)) for network in networks))

정석적으로는 깊이우선탐색이나 너비우선탐색을 이용하면 될 것 같습니다. 
stack이 queue보다 구현이 쉽기 때문에 (리스트를 바로 쓰면 되니까요) stack을 사용하였습니다.
즉 깊이 우선 탐색(dfs)인 것이죠.  

1번 컴퓨터부터 하나씩 탐색을 진행하여 더 이상 연결되는 곳이 없을 때까지 탐색합니다. (=네트워크)
탐색이 끝나면 visited에 기록된 노드를 marked에 옮겨 기록합니다.
옮길 때는 시작한 노드를 기록하여 시작 노드에서 도달할 수 있는 하나의 네트웍임을 명시적으로 기록합니다. 
그리고 이 기록이 있는 노드에서는 출발할 필요가 없으니 Pass 합니다. 

def solution(n, computers):
    def search(start):
        stack = [start]
        visited = {start}
        while stack:
            v = stack.pop()
            for w in networks[v]:
                if w not in visited:
                    stack.append(w)
                    visited.add(w)
        return visited

    networks = [{i} for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            if computers[i][j] == 1:
                networks[i].add(j)
                networks[j].add(i)
    marked = [None for _ in range(n)]
    for start in range(n):
        if marked[start] is None:
            for v in search(start):
                marked[v] = start
    return len(set(marked))

 

고(go)

func solution(n int, computers [][]int) int {
	var networks []map[int]bool
	for i := 0; i < n; i++ {
		networks = append(networks, map[int]bool{i: true})
	}
	for n1 := 0; n1 < n; n1++ {
		for n2 := n1 + 1; n2 < n; n2++ {
			if computers[n1][n2] == 1 {
				idx1, idx2 := -1, -1
				for idx, _ := range networks {
					if is_in(n1, networks[idx]) {
						idx1 = idx
					}
					if is_in(n2, networks[idx]) {
						idx2 = idx
					}
				}
				if idx1 != idx2 {
					networks = append(networks, union(networks[idx1], networks[idx2]))
					if idx1 > idx2 {
						networks = append(networks[:idx1], networks[idx1+1:]...)
						networks = append(networks[:idx2], networks[idx2+1:]...)
					} else {
						networks = append(networks[:idx2], networks[idx2+1:]...)
						networks = append(networks[:idx1], networks[idx1+1:]...)
					}
				}
			}
		}
	}
	return len(networks)
}

func is_in(n int, network map[int]bool) bool {
	for com := range network {
		if n == com {
			return true
		}
	}
	return false
}

func union(a map[int]bool, b map[int]bool) map[int]bool {
	c := map[int]bool{}
	for each := range a {
		c[each] = true
	}
	for each := range b {
		c[each] = true
	}
	return c
}