You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
def solution(n, computers):
answer = 0
graph = [[] for _ in range(n)]
visited = [False]*n
# graph = [[1번 컴에 연결된 n번 컴터], ... ]
# 여기에는 각 그래프 1번 컴퓨터에 연결된 컴퓨터들을 추가하는 것
for i in range(0, n):
for j in range(0, n):
if computers[i][j] == 1 and i != j:
graph[i].append(j)
# 그래프를 돌 dfs도 만들었음
def dfs(x):
visited[x] = True
for i in graph[x]:
if not visited[i]:
dfs(i)
# 컴터 개수만큼 dfs를 도는데 이때 연결된 네트워크 counting (처음 도는 dfs를 여기서 counting)
for i in range(n):
if not visited[i]:
answer += 1
dfs(i)
# print(answer)
return answer
느낀점
몬가,, 연결요소 문제 풀이를 완벽한 이해가 아닌 기억력을 바탕으로 풀다보니, 약간 흠.. 애먹는 부분이 없지 않아있다..
문제 풀이
연결 요소 문제들은 이제 dfs라는 것이 자동으로 나올 정도
BOJ와 다르게 여기서는 연결된 것들끼리 1,0으로 표시해서 줘서 내가 직접 graph에 computer 배열에서 빼서 꽂아줘야 했다.
이제 완벽하게 알게 된 것은 graph는 2차원 배열로 graph의 인덱스는 각 컴터 번호이고, 그 컴터 별 연결된 컴터들의 번호를 각 배열에 넣어줘야 한다.
dfs 돌고 난후에 컴터 개수 n개 만큼 for 문을 돌아서 dfs가 처음 도는 것을 counting -> 즉, 노드 덩어리를 겟하는 것을 잊지말자! 숙지하자!
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
-
https://school.programmers.co.kr/learn/courses/30/lessons/43162
문제 설명
느낀점
문제 풀이
dfs가 처음 도는 것
을 counting -> 즉, 노드 덩어리를 겟하는 것을 잊지말자! 숙지하자!⭐️ dfs가 처음 도는 것을 counting 해주는 게 바로 뭐냐?
Beta Was this translation helpful? Give feedback.
All reactions