접근법
두 가지 접근법으로 이 문제를 풀 수 있습니다. 먼저 첫 번째 접근법은 깊이 우선 탐색(DFS)를 사용한 접근 방법이고, 두 번째 방법은 집합을 사용한 풀이입니다.
(1) 깊이 우선 탐색(DFS)
먼저 노드를 방문했는지 확인하는 visited 리스트를 컴퓨터의 수 만큼 생성한 뒤 0으로 초기화 시킵니다. 그리고 방문하지 않은 컴퓨터일 경우에는 방문한 뒤, 1로 바꿔주고, 다른 컴퓨터를 모두 확인하여 방문되지 않았고, 연결이 되어있는(관계가 1인) 경우가 있을 경우 계속해서 방문해 줍니다. 이렇게 더이상 방문할 컴퓨터가 없을 경우, visited값이 0인 다른 컴퓨터를 새로 방문하여 이 과정을 반복해 줍니다.
(2) 집합을 사용한 풀이
두 컴퓨터의 관계성을 나타내는 행렬은 대각선을 기준으로 대칭이기 때문에 오른쪽 위의 값만을 사용하였습니다. 먼저 컴퓨터의 수만큼 그 값을 집합으로 선언해 주고, 하나의 리스트에 넣어줍니다. 이제 위의 행렬을 하나씩 접근하여 행렬 값이 1인 경우에 각 행, 렬이 속한 집합을 찾아주고, 두 집합이 다를 경우에 하나의 집합으로 합해주면 됩니다!
나의 코드
def dfs(computers, visited, start):
record = [start]
while record:
j = record.pop()
if visited[j] == 0:
visited[j] = 1
for i in range(0, len(computers)):
if computers[j][i] ==1 and visited[i] == 0:
record.append(i)
def solution(n, computers):
answer = 0
visited = [0]*n
start = 0
while 0 in visited:
if visited[start] ==0:
dfs(computers, visited, start)
answer +=1
start+=1
return answer
