프로그래머스(programmers) 네트워크 python 정답[DFS 풀이]

프로그래머스(programmers) 네트워크 python 정답[DFS 풀이]

문제 링크

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

프로그래머스

문제 이미지

 

 

문제 정답

from collections import defaultdict, deque
def solution(n, computers):    
    visited = [False] * (n)
    answer = 0
    graph = defaultdict(set)
    # 그래프 만들기
    for i in range(len(computers)):
        for j in range(len(computers[i])):
            if computers[i][j] ==1 :
                addGraph(graph,i,j)
                addGraph(graph,j,i)                
    # 방문 여부 판단하기
    for start in range(n):
        # 모든 정점을 시작점으로 Test
        if not visited[start]:
            answer +=1
            dfs(graph,visited,start)            
    return answer

def addGraph(graph,i,j):
    graph[i].add(j)
    graph[j].add(j)
    
def dfs(graph,visited,start):
        if visited[start]:
            return
        else:
            visited[start] = True
            for to in graph[start]:
                dfs(graph,visited,to)
        return

문제 해설

일반적인 그래프 방문 문제와 유사하다

다른점이 있다면, 최단거리나 mst 경로를 찾는 것이 아니라, 끊어져 있는 그래프가 몇 개가 있는지 찾는 것이다.

• 무방향 그래프를 만들어주고
• 각 점에 대해서 그래프 순회를 시작하여 갈 수 있는 점을 방문한다
  • 만약 다음 점에서 다시 그래프 순회를 시작할 수 있다면, 끊어진 그래프가 있는 것이므로 answer를 하나 더해준다