[프로그래머스/파이썬] 네트워크 풀이 ( dfs , 재귀함수, Python )

[프로그래머스 / 파이썬] 네트워크 풀이 

( dfs , 재귀함수, Python )

 

 

1. 문제

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

프로그래머스

---

 

2. 문제 해결 아이디어 (풀이)

 

문제 이해를 위한 예시

 

1. 반복문으로 모든 노드를 1~n번까지 DFS로 탐색하면서, 하나의 노드 당 연결된 모든 노드를 방문처리한다.

* 이때, 방문 처리 배열 'visited'를 만들어서 이용한다. 

 

1.1. 이때 현재 노드와 연결된 모든 노드를 for문으로 반복하여서,

아직 방문하지 않은 노드인지(+ 벽이 아닌 길인지) 확인한 뒤, dfs로 계속 방문해 주면 된다.

 

 

2. 방문하지 않았던 새로운 노드에 들어오면 네트워크 개수를 1 증가시키고,

다시 DFS로 연결된 모든 노드를 방문처리한다. 

 

2.1. 이미 방문한 노드는 DFS를 수행하지 않고 바로 끝낸다.

 

---

 

3. 코드

def dfs(computers, node, visited):
    # 나자신은 방문처리 
    # 나자신 이미 방문했으면 False return (그러면 건너뛰고 다음 노드를 탐색한다.)
    if visited[node]:
        return False
    
    visited[node] = True # 현재 도착한 노드는 방문처리 

    # 현재 노드와 연결된 다른 노드도 방문해보자.
    for i in range(len(computers[node])):    
        # 연결된 다른 노드 하나하나 방문 
        # 만약 연결 되어 있는 노드라면?
        if computers[node][i] == 1:
            #아직 방문 안했다면?
            if not visited[i]:
                #해당 노드도 dfs 진행해서, 각 연결된거 모두 방문처리 하기.
                dfs(computers, i, visited)
    # - 방문 모두 끝났기 때문에 True 반환
    return True
    
    


def solution(n, computers):
    count = 0
    answer = 0
    visited = [False] * n # 방문처리할 것
    
    for i in range(n):
        # print('dfs 실행!', i)
        if dfs(computers, i, visited):
            count+=1
        # print(count)
    
    # print(count)
    return count

 

 

 

---

4. 마무리

방문 처리까지는 했는데, 네트워크 개수를 세는 로직에서 조금 고민을 더 했다. 

DFS를 조금이나마? 이해 한 것 같다.

 

- 함께 공부한 자료

https://www.youtube.com/watch?v=7C9RgOcvkvo