🛠 문제
👩🏻💻 해결 방법
visit이 0일 경우, dfs를 통해 visit을 1로 처리해주고 재귀를 통해 연관된 노드들을 모두 방문처리해준다
소스 코드
# dfs를 사용한 풀이
def dfs(n, computers, now, visit):
visit[now] = 1
for i in range(n):
if i != now and computers[now][i] == 1:
if visit[i] == 0:
dfs(n, computers, i, visit)
def solution(n, computers):
answer = 0
visit = [0] * n
for i in range(n):
if visit[i] == 0:
dfs(n, computers, i, visit)
answer += 1
return answer
# bfs를 사용한 풀이
from collections import deque
answer = 0
def bfs(n, computers, visit, now):
q = deque()
q.append(now)
visit[now] = 1
while q:
i = q.popleft()
for j in range(n):
if computers[i][j] == 1 and visit[j] == 0:
visit[j] = 1
q.append(j)
def solution(n, computers):
visit = [0] * n
global answer
for i in range(n):
if visit[i] == 0:
bfs(n, computers, visit, i)
answer += 1
return answer💡 다른 사람의 풀이
플로이드 워셜 알고리즘 사용
def solution(n, computers):
temp = []
for i in range(n):
temp.append(i)
for i in range(n):
for j in range(n):
if computers[i][j]:
for k in range(n):
if temp[k] == temp[i]:
temp[k] = temp[j]
return len(set(temp))