[Level 2] 네트워크

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

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

---

접근

DFS로 연결된 컴퓨터를 탐색하였다. 방문하지 않은 컴퓨터가 있을 때 방문하여 연결된 모든 컴터를 탐색하였다. 이렇게되면 DFS 탐색을 할 때마다 최종해를 카운트해주면 된다.

 

구현

방문 표시를 할 visited 리스트를 초기에 False로 초기화해줬다.

visited = [False for _ in range(n)]

 

0번부터 탐색을 하여 방문하지 않은 컴퓨터가 있으면 answer를 증가시키고 DFS를 할 준비를 한다.

스택을 생성하여 해당 컴퓨터 번호를 넣고 방문 표시를 해준다.

for idx in range(n):
        if not visited[idx]:
            answer += 1
            visited[idx] = True
            stack = []
            stack.append(idx)

 

DFS를 실행하여 연결된 컴퓨터 중 방문하지 않은 컴퓨터를 찾아 방문표시를 한다.

while stack:
	top = stack.pop()
	for x in range(n):
		if not visited[x] and computers[top][x]:
			visited[x] = True
			stack.append(x)

---

전체 코드

def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]
    
    for idx in range(n):
        if not visited[idx]:
            answer += 1
            visited[idx] = True
            stack = []
            stack.append(idx)
            while stack:
                top = stack.pop()
                for x in range(n):
                    if not visited[x] and computers[top][x]:
                        visited[x] = True
                        stack.append(x)
                        
    
    
    return answer