https://programmers.co.kr/learn/courses/30/lessons/43162
연결에 대한 이차원 배열이 주어졌을 때, 연결된 네트워크 개수를 return 하는 문제다.
1
을 return, 방문한 정점이면 연결된 네트워크이므로 0
을 return 해준다.answer
변수에 더해준다.
import sys
def solution(n, computers):
graph = {}
visited= [0]* n
answer = 0
for row_index,rows in enumerate(computers):
for num_index,num in enumerate(rows):
if num==1 :
if row_index not in graph:
graph[row_index]=[num_index]
else:
graph[row_index].append(num_index)
#print(graph)
def dfs(index):
#방문한 곳이 아니므로 연결되어 있지 않다 = 다른 네트워크이므로 return 1
if visited[index]==0:
visited[index] = 1
while (graph[index]):
dfs(graph[index].pop(0))
return 1
#방문한 곳이므로 연결되어 있다 = 같은 네트워크이므로 return 0
else:
return 0
for i in range(n):
answer += dfs(i)
return answer
한달전에 푼 문제인데, 이제 보니 그래프를 따로 만들지 않아도 된다.
그냥 computers를 이용하면 된다.
import sys
def solution(n, computers):
graph = {}
visited= [0]* n
answer = 0
def dfs(index):
if visited[index]==0:
visited[index] = 1
for j in range(len(computers)):
if computers[index][j]==1:
dfs(j)
computers[index][j] = 0
for i in range(n):
if visited[i]==0:
dfs(i)
answer += 1
return answer