[프로그래머스 lv 3] 네트워크

사용 언어 - Python3

문제 - 네트워크

프로그래머스

 

 

정답

재귀적인 DFS 문제 (정답 맞춘 여부 X)

1. visited 방문여부 리스트 생성

2. for문을 두개 만들어서 인덱스 com, connect를 비교

값이 1이고, 방문여부가 False인 노드를 또 DFS 재귀함수를 돌리는 구조

com 인덱스를 방문한 후, com에서 connect 인덱스를 방문하기 때문에 DFS(n,computers,connect,visited)로 바뀜

방문한 connect를 기준으로 또 새로운 노드를 방문하려고 하는 재귀함수이다.

3. DFS에서 모든 노드를 방문했으면 answer += 1 횟수추가

# dfs 이용
def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1     
    return answer

def DFS(n, computers, com, visited):
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1:
            if visited[connect] == False:
                DFS(n, computers, connect, visited)

 

 

 

---

레퍼런스

• 정답 참고

프로그래머스 - 네트워크 (DFS, BFS) Python

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부