[프로그래머스/Python] 네트워크 - Level3

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

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

이 문제는 DFS(깊이 우선 탐색) 문제이다. 끝까지 탐색하면서 네트워크를 개수를 세면 된다. 

코드를 짜고 실행해보는데  에러가 발생했다. 찾아보니 재귀함수 호출이 너무 많아서 그런거였다. 코드 구조도 바꾸어 봤는데도 계속 이 에러가 떠서 다른 사람 코드를 보고 구조를 똑같이 했는데도 에러가 났다... 그러던 중 코드에서 변수를 잘못 입력해서 (j 자리에 i를 넣음..) 재귀함수가 너무 많이 호출된 거였다... 해결해서 다행이었다 ㅜ

 

 

def solution(n, computers):
    answer = 0
    visited = [False] * n # 방문한 컴퓨터인지 확인하는 리스트
    
    for i in range(n):
        if visited[i] == False: # 방문하지 않았다면 DFS 수행
            dfs(i, n, computers, visited)
            answer += 1 # DFS 수행이 다 끝나면 answer에 +1
    
    return answer

# DFS 를 수행하는 메서드
def dfs(i, n, computers, visited):
    visited[i] = True 
    for j in range(n):
        if i != j and computers[i][j] == 1 and visited[j] == False: # 연결된 컴퓨터가 방문하지 않았다면 DFS 수행
            dfs(j, n, computers, visited)

DFS 는 재귀함수를 사용하면 됩니다. 방문한 컴퓨터인지 확인하는 리스트를 두어 방문하지 않았다면 DFS를 수행합니다. 더 이상 방문할 컴퓨터가 없다면 answer에 +1 을 해줍니다. dfs() 메서드는 DFS 를 수행하는 메서드입니다. 현재 위치의 컴퓨터를 방문한 값(True) 로 바꾸고 연결된 컴퓨터를 확인해 연결된 컴퓨터를 방문하지 않았다면 DFS를 수행합니다.