〔프로그래머스/파이썬〕네트워크(DFS)

출처

프로그래머스

 

 

---

 

풀이

def dfs(start, visited, computers):
    # 현재 노드 방문
    visited[start] = True
    for i, connected in enumerate(computers[start]):
        # 자기자신이 아니면서 아직 방문하지 않은 인접 노드 방문
        if i != start and connected == 1 and visited[i] == False:
            dfs(i, visited, computers)
    return visited

def solution(n, computers):
    answer = 0
    visited = [False] * n
    while False in visited:
        start = visited.index(False)
        visited = dfs(start, visited, computers)
        answer += 1
    return answer

 

---

 

노트

• 연결된 네트워크의 개수를 구하는 문제
• 처음에는 플로이드-워셜을 써야하는건가 DFS 를 쓰는건가 헷갈렸는데, 최소 거리가 중요하지 않고 단순히 네트워크의 개수를 세는 것이기 때문에 DFS 가 적합