https://programmers.co.kr/learn/courses/30/lessons/43162
문제
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
- 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
- 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
- i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
- computer[i][i]는 항상 1입니다.
입출력 예
입력 | n: 3, computers: [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
출력 | 2
풀이
이 문제는 재귀함수를 사용한 DFS로 구현했다. 하나의 컴퓨터를 깊게 방문하고 그 작업이 끝나면 네트워크 갯수를 1 증가시켜 줌으로써 총 네트워크 갯수를 구할 수 있다.
먼저 방문 처리를 위해 길이가 n(컴퓨터 갯수)인 visited 리스트를 생성한다. 연결된 컴퓨터들을 찾기 위해 첫번째 컴퓨터부터 마지막 컴퓨터까지 for문으로 순회하며 방문하지 않은 컴퓨터라면 computers, visited, i(컴퓨터 인덱스)를 매개변수로 하는 dfs 함수를 실행한다. dfs 함수가 끝나면 네트워크 갯수를 1 증가시켜주고, 이 반복문이 끝나면 네트워크의 갯수를 리턴한다.
dfs 함수는 현재 컴퓨터인 i번째 컴퓨터를 방문처리하고 현재 컴퓨터와 연결된 컴퓨터를 찾기 위해 다시 for문을 실행시킨다. 이 반복문에서는 현재 컴퓨터가 아니면서 현재 컴퓨터와 연결된 인덱스라면 다시 dfs 함수에 자신의 인덱스를 넣어 한 층 더 깊이 들어갈 수 있다. 이렇게 재귀함수를 통해 방문한 컴퓨터를 체크하면서 다시 방문하지 않도록 하고, 자신과 연결된 가장 깊은(큰 숫자의) 컴퓨터까지 확인하면 dfs 함수가 종료된다.
코드
def solution(n, computers):
answer = 0
visited = [0] * n
for i in range(n):
if not visited[i]:
dfs(computers, visited, i)
answer += 1
return answer
def dfs(computers, visited, i):
visited[i] = 1
for j in range(len(visited)):
if not visited[j] and computers[i][j]:
dfs(computers, visited, j)