문제 설명
네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 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입니다.
알고리즘
문제가 살짝 이해가 안됐는데, 다시 읽어보니, 연결된 컴퓨터들은 하나의 네트워크로 묶고, 연결되지 않은 컴퓨터는 다른 네트워크로 분류하여 네트워크의 개수를 구하는 문제였다.
제한 사항을 먼저 살펴보면, 컴퓨터는 1이상 200개 이하고, index는 0번부터 시작한다.
무조건 computer[i][i] = 1 이고, i번 컴퓨터와 j번 컴퓨터가 연결되어있으면 computer[i][j] = 1, computer[j][i] = 1 이다.
컴퓨터를 노드로 생각을 하면 간단한 DFS 문제라고 생각이 된다.
-
0번 컴퓨터부터 n-1번 컴퓨터까지 차례대로 반복문을 돌리면서, 방문한적이 없으면 그 컴퓨터를 방문하여 인접한 컴퓨터가 있는지 찾고, 있다면 그 컴퓨터를 방문한다.
-
이런 식으로 인접한 컴퓨터를 먼저 다 방문을 하고 나면, 아직 방문을 하지 않은 컴퓨터들이 많이 남아있을 것이다. 어차피 반복문이 끝나지 않았기 때문에 방문 하지 않은 컴퓨터들도 방문을 하게 될 것이다.
-
중요한 것은 인접하지 않은 컴퓨터를 방문하는 것으로 넘어갈 때, 네트워크의 개수를 1 증가 시켜주는 것이다.
정답 코드
def solution(n, computers):
isvisited = [False] * n # 0부터 n-1번 컴퓨터를 방문했는지 여부. 네트워크 수를 결정할 때 중요하다.
answer = 0
for num in range(n):
answer += DFS(n,computers,isvisited,num)
return answer
def DFS(n, computers, isvisited, k):
if not isvisited[k]: # 노드(컴퓨터)를 방문한 적이 없다면
isvisited[k] = True
for i in range(n): # 인접해있는지 확인.
if computers[k][i] == 1 and not isvisited[i]: # 인접해있고 방문한 적이 없다면
DFS(n,computers,isvisited,i) # 방문하자!
return 1
return 0 # 방문한 적이 있으므로 넘겨야 한다.여기서 나는 return 문을 가지고 네트워크의 개수를 증가시켜주는 방법을 사용했다. 인접한 컴퓨터가 아무리 많아도 결국 최종적으로는 answer가 1만 증가되게 만든 것이다.
이번 문제는 쉽게 풀려서 기분이 좋았다. 끝!
