[python] 프로그래머스_네트워크 (DFS&BFS)

문제

 

풀이

모든 컴퓨터를 돌면서 방문 안한 위치에 방문하여 DFS를 수행하여 풀 수 있다. 

하나의 DFS가 종료되면 +1 해서 네트워크 수를 계산하고, DFS 함수는 해당 위치를 방문처리하고 모든 컴퓨터를 for문으로 확인하면서 자기 자신이 아니고 연결되어 있는 경우 그리고 방문을 안한 경우에 DFS로 방문처리한다.

 

코드

def solution(n, computers):
    answer = 0
    visited = [False]*n # 컴퓨터 개수 만큼
    for com in range(n): # 각 컴퓨터를 돌면서 방문 안했으면 DFS
        if visited[com] == False :
            DFS(n, computers, com, visited)
            answer +=1 # 연결된 하나의 네트워크 +1
    return answer
            
            
def DFS(n, computers, com, visited):
    visited[com] = True # 방문처리
    for connect in range(n): # 컴퓨터 개수만큼 for문 돌면서
        if connect != com and computers[com][connect] == 1: # 자기 자신이 아니고 com과 connect가 연결되어 있고
            if visited[connect] == False :  # 방문 안했으면
                DFS(n, computers, connect, visited) # DFS