https://programmers.co.kr/learn/courses/30/lessons/43162

Problem

그래프상에서 연결요수개수의 집합 개수를 묻는 문제

Solution

adj 를 통해 인접 리스트를 DFS 방문

코드설명

1)adj배열을 통해 인접행렬을 최소화
2)adj의 각 idx값을 방문하면서 visited여부 판단
3)방문이 안되어있으면 다시 dfs호출

Python Code

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

cnt=0

def dfs(start,visited,adj):
     visited[start]=True

     for e in adj[start]:
         if not visited[e]:
             dfs(e,visited,adj)



def solution(n, computers):
    global cnt
    visited=[False]*(n)
    adj=[[] for _ in range(len(computers))]
    for i in range(0,len(computers)):
        for j in range(0,len(computers[i])):
            if computers[i][j]==1:
                adj[i].append(j)
    for i in range(0,len(computers)):
        if not visited[i]:
            cnt+=1
            dfs(i,visited,adj)
solution(n,computers)
print(cnt)