문제
해당 문제는 사실 문제에서 부터 dfs/bfs 문제라고 주어져 있다. 다만 처음에 이 문제를 보고 플로이드 워셜로도 풀 수 있겠다고 생각이 들었는데 이 알고리즘으로 문제를 풀려고 하니 잘 안풀려서 일단 dfs 알고리즘으로 문제를 해결해주었다.
dfs알고리즘으로 해결하는 방법은 간단하게 n개의 컴퓨터를 모두 방문해주는데
i번째의 컴퓨터를 방문할 때 해당 컴퓨터와 연결된 컴퓨터를 함수안에서 모두 방문해준 후 answer을 +1 해주면 하나의 네트워크에 대해서 카운트를 해주는 코드가 된다.
def solution(n, computers):
answer = 0
visited = [False]*n
def dfs(i):
visited[i] = True
for j in range(n):
#아직 방문안한 컴퓨터이며 i번째 컴퓨터와 연결된 컴퓨터 방문
if visited[j]==False and i != j and computers[i][j] == 1:
visited[j] = True
dfs(j)
for i in range(n):
# 각 컴퓨터별로 방문하여 확인
if visited[i] == False:
dfs(i)
#i번째 컴퓨터, 그리고 이 컴퓨터와 연결된 컴퓨터 모두 방문 후 +1
answer+=1
return answer해당 문제를 플로이드 워셜 알고리즘을 통해서 풀게 되면
def solution(n, computers):
answer = 0
tmp = [i for i in range(n)]
for i in range(n):
for j in range(n):
if computers[i][j] == 1 and i != j:
for k in range(n):
if tmp[k] == tmp[i]:
tmp[j] = tmp[i]
answer = len(set(tmp))
return answer
이렇게 된다.
dfs/bfs 또는 플로이드워셜 알고리즘을 알고있더라고 문제의 조건에 맞게 변형해서 코드를 작성해주는게 어려웠던 문제였다.
