문제

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

풀이

시도 1

  • BFS (재귀)를 사용한다. 네트워크 수는 트리의 갯수와 같으며 트리의 갯수만큼 visit 했는지 여부를 처음엔 False로 선언하고 BFS를 돌면서 방문 할 때마다 True로 변경해준다
solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


def DFS(n, computers, node, visited):
	# 현재 노드를 방문 처리
    visited[node] = True
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for connect in range(n):
        if connect != node and computers[node][connect] == 1:
            if visited[connect] == False:
                DFS(n, computers, connect, visited)

def solution(n, computers):
    visited = [False] * n
    answer = 0
    # 트리의 갯수=n
    for node in range(n):
        if visited[node] == False:
            DFS(n, computers, node, visited)
            answer += 1
    return answer

다른사람풀이

DFS 스택을 이용

solution.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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