프그스_DFS BFS_네트워크_레벨3 (그래프 탐색 활용_고득점 kit)

• 링크 : https://programmers.co.kr/learn/courses/30/lessons/43162

---

3 [[1, 1, 0], [1, 1, 0], [0, 0, 1]] 2
3 [[1, 1, 0], [1, 1, 1], [0, 1, 1]] 1

---

• 여기서 n=3일 때 2차원 배열 안에 있는 각각의 배열들이 하나의 노드임

• 그 노드가 A번 노드, B번 노드, C번 노드이고

• A번 노드가 [1, 1, 0]일 경우 자기 자신과 B번 노드와 연결된 것 ([자기자신, B, 0])

• B번 노드가 [1, 1, 0]일 경우 자기 자신과 A번 노드와 연결된 것 ([A, 자기자신, 0])

• C번 노드의 경우 [1, 0, 0]이면 자기 자신만 연결되어있는것

---

• 풀이 생각한거
  혹시 이건가 지금 그래프가 하나 주어졌잖아, DFS로 탐색하면서 방문한 노드는 visit = True로 체크해 => 이때 순회 하나 끝나면 answer += 1 (네트워크 1개)

다음 DFS로 탐색하면서 방문하지 않은 노드 찾아서 DFS 탐색해 => 위랑 마찬가지로 visit 체크하면서 순회 하나끝나면 또 answer += 1 이렇게

---

• 참고 블로그 링크 : https://velog.io/@timointhebush/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-DFS-BFS-Python

''' 블로그 (못풀었다...) '''

def solution(n, computers):
    answer = 0
    visited = [False] * n
    
    # (중요) 여기서(main에서) DFS 기본틀 수행시킴
    for node_idx in range(n):                     # node_idx = 그래프 순회의 시작노드 
        if visited[node_idx] == False:            # 모든 노드 순서대로 방문하지 않은 노드 방문 시작
            dfs(n, computers, visited, node_idx)  # 방문하지 않은 노드의 인덱스도 넣어줌
            answer += 1                           # DFS 순회 하나 끝나면 그래프 1개
    return answer
    

# 각 시작점에 대해서부터 dfs 수행(방문하지 않았던 노드만)
def dfs(n, computers, visited, node_idx):         # node_idx = 그래프 순회의 시작노드
    visited[node_idx] = True
    
    for other_idx in range(n):
        # 자기 자신 노드가 아니면서, 1인 경우(= 다른 노드와 연결된 경우)
        if other_idx != node_idx and computers[node_idx][other_idx] == 1:
            if visited[other_idx] == False:
                dfs(n, computers, visited, other_idx) # 다른 노드로 이동

print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]), end="\n\n")
print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

---

''' 몇일 후 내가 다시 푼 '''
def solution(n, computers):
    answer = 0
    visit = [False] * n
    
    for i in range(n):
        if not visit[i]:
            visit[i] = True
            dfs(computers, i, visit, n)   # n은 range(len(n)) 안하려고 넣음(시간복잡도)
            answer += 1                   # dfs 1회 끝나면 네트워크 1개 파악된 것
    return answer

def dfs(comp, i, visit, n):    
    for j in range(n):
        if not visit[j]:                 # 방문하지 않은 노드에 대해서만
            if i == j and i == 1:        # 자기 자신으로 연결은 스킵
                continue
            elif comp[i][j] == 1:        # 그 외에 연결된 경우 DFS
                visit[j] = True
                dfs(comp, j, visit,n)
    
    
print(solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]), end="\n\n")
print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))