문제
이 문제는 네트 워크 상 컴퓨터끼리의 서로 연결 유무를 나타낸 lists 가 있을 때,
네트워크 덩어리가 몇 개인지 구하는 문제이다.
처음에는 감을 못 잡았지만, 천천히 고민하며 한 노드와 연결된 모든 노드를 재귀적으로 찾도록 dfs 방식을 활용하고, 다 찾은 경우에 개수를 +1 해주도록 작성했다.
여기서 visited가 필요한 이유는,
탐색 중에 걸리는 모든 노드는 재귀적으로 연결된 모든 노드를 확인하기 때문에
한번 본 노드는 볼 필요 없으므로 체크하기 위함이다.
아래는 solution이며 블로그를 참고하여 풀었다.
def dfs(start, n, computers, visited):
visited[start] = True
for node in range(0, n):
if visited[node] == False and computers[start][node] == 1:
visited = dfs(node, n, computers, visited)
return visited
def solution(n, computers):
answer = 0
visited = [False] * n
for i in range(n):
if visited[i] == False:
dfs(i, n, computers, visited)
answer += 1
return answer
