프로그래머스 level 3- 네트워크

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

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

 

#Idea

: 주로 dfs는 인접그래프로 많이 문제를 풀었는데, 배열로 풀어야 해서 살짝 헷갈리는 부분이 있었다.

그렇지만 별다를 것 없이 각 index를 edge로 생각해서 한 노드부터 아직 방문한 적이 없고 인접한 노드로 dfs를 해나가면 그 노드와 연결되어있는 연결 성분을 찾을 수 있다. 그리고 이전 시작 노드와 연결되어있지 않아 아직 방문되지 않은 노드 중에 가장 작은 index를 가진 노드를 그 다음으로 해서 또 dfs를 해나간다..

이렇게 연결되어있는 연결 성분, 문제에서는 네트워크의 개수를 찾으면 된다.

+) 연결 성분이라길래 dfs두 번 하는 그 방식을 떠올렸는데 이건 무향 그래프라 한번만 하면 연결 성분이 나오는 듯.

이렇게 네트워크의 개수를 찾으면 된다!

 

#풀이

def dfs(node,computers,visited):
	visited[node]=True
    for i,adjExist in enumerate(computers[node]):
    	if adjExist>0 and i!=node and visited[i]==False: 
        	#인접노드가 존재하고, 자기 자신이 아니며, 인접 노드를 아직 방문하지 않았다면 dfs
            dfs(i,computers,visited)
    return visited
   

def solution(n,computers):
	 answer=1
     visited=[False]*n
     startNode=0
     while True:
     	visited=dfs(startNode,computers,visited)
        if False in visited: #아직 덜 방문하고, 앞선 노드와 network를 이루지 않는 노드가 존재하면
        	answer+=1 #네트워크 수를 늘린다.
        else:
         	break #모든 노드를 방문했다면 break
            
      return answer