[프로그래머스] 네트워크 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

1. 컴퓨터들 간의 연결을 그래프로 나타내기 위해 리스트를 생성한다. graph = list()
2. 컴퓨터 수만큼 반복하며 for _ in range(n)
3. 각 컴퓨터 별로 연결된 컴퓨터의 정보를 저장할 공간을 만들어준다. graph.append([])
4. 컴퓨터 수만큼 반복하고 for i in range(n)
5. 각 컴퓨터 별로 연결된 컴퓨터를 파악하기 위해 반복하며 for j in range(n)
6. 만약 같은 컴퓨터 번호가 아니고 두 컴퓨터가 연결되어 있으면 if (i != j) and (computers[i][j] == 1)
7. 해당 컴퓨터의 연결을 그래프에 추가한다. graph[i].append(j)
8. 각 컴퓨터 별로 탐색을 확인할 리스트를 생성하고 탐색하기 전으로 초기화한다. result = [False] * n
9. 깊이 우선으로 탐색하며 네트워크 수를 파악하기 위해 깊이 우선 탐색을 수행할 함수를 생성한다. def dfs(start)
10. 시작 위치의 탐색 결과를 탐색했다고 바꾼다. result[start] = True
11. 그리고 시작 위치에서 연결된 컴퓨터들을 하나씩 방문하여 탐색을 진행하는데 for i in graph[start]
12. 만약에 해당 컴퓨터가 처음 방문되었을 경우 if (not result[i])
13. 해당 컴퓨터에서 다시 연결된 컴퓨터를 먼저 탐색한다. dfs(i)
14. 해당 깊이 우선 탐색 함수는 모든 컴퓨터를 방문하며 for i in range(n)
15. 만약 해당 컴퓨터를 처음 방문했을 경우 if (not result[i])
16. 함수를 수행하고 dfs(i)
17. 함수를 수행하면 한 네트워크를 파악할 수 있으므로 네트워크 개수를 1 증가시킨다. answer += 1

반응형

3. 소스코드

def solution(n, computers):
    answer = 0
    
    graph = list()
    for _ in range(n):
        graph.append([])
        
    for i in range(n):
        for j in range(n):
            if (i != j) and (computers[i][j] == 1):
                graph[i].append(j)
    
    result = [False] * n
    
    def dfs(start):
        result[start] = True
        
        for i in graph[start]:
            if (not result[i]):
                dfs(i)
    
    for i in range(n):
        if (not result[i]):
            dfs(i)
            answer += 1
    
    return answer