[Python] DFS/BFS : 프로그래머스 LV.3 네트워크

프로그래머스

문제 설명:

자세한 문제 설명은 위의 링크에서 확인하자. 내가 이해한 문제의 설명은 간단히 정리하자면, computers라는 각각의 연결정보가 들어있는 리스트와 총 컴퓨터 개수 n이 주어졌을때, 총 몇개의 네트워크로 구성되어 있는지 구하는 문제이다. 여기서 네트워크란 그래프 자료구조에서의 노드 간선과 같다고 이해하였다. 

문제 해설:

나는 이 문제를 깊이우선탐색 알고리즘으로 접근하였다. 

우선, 방문한 컴퓨터(노드)를 확인하고 그 값을 저장 할수 있는 visited 변수를 만들어주고, 반복문을 통해 방문하지 않은 컴퓨터라면, 현재 해당 컴퓨터와 연결되어 있는 모든 컴퓨터를 탐색할수 있게 dfs라는 함수를 호출해준다.
dfs함수에서 visited변수의 값을 방문한 컴퓨터에 맞게 정보를 업데이트 시켜주며 연결된 컴퓨터 또한 찾게된다. 이때, dfs함수가 끝이 나면 더 이상의 연결된 컴퓨터가 없는 것이기때문에 하나의 덩어리 즉, 네트워크 값을 1 증가 시켜준다. 이 과정을 반복하면 연결된 브랜치가 총 몇개인지 구할수 있게된다!

#네트워크

#    0  1  2
# 0 [1, 1, 0]
# 1 [1, 1, 0]
# 2 [0, 0, 1]

#2번째 함수 dfs로 연결된 컴퓨터 확인시작
def dfs(computers, visited, i):
    visited[i] = True  # 현재 방문한 컴퓨터 방문 확인하기
    
    #연결되어있는 컴퓨터 확인하기
    for j in range(len(computers)): # 컴퓨터 대수 만큼 반복
        if computers[i][j] == 1 and not visited[j]:  # i번 컴퓨터와 연결되어 있고, 아직 방문하지 않은 컴퓨터라면
            dfs(computers, visited, j)  # 해당 컴퓨터로 DFS 탐색
# 첫번째로 solution 함수 실행 시작
def solution(n, computers):
    network = 0
    visited = [False] * n  # 컴퓨터 방문 여부를 나타내는 리스트
    
    for i in range(n):
        if visited[i] == False:  # 아직 방문하지 않은 컴퓨터라면
            dfs(computers, visited, i)  # 2번째 함수 DFS 탐색 수행
            network += 1  # 네트워크 개수 증가
    
    return network

n = 3
computers = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

print(solution(n, computers))