프로그래머스 level 3 - 네트워크 (DFS/BFS)

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

computers = [[1, 1, 0, 0], [1, 1, 0 0], [0, 0, 1, 1], [0, 0, 1, 1]]

n = 4인 그래프에서 visited = [0] * 4 배열을 생성한다.

visited[1] = 1이면 1번 그래프는 이미 방문한 것이다.

0, 1, 2, 3번 그래프를 순회하면서

-> 0번에서 1번 그래프가 연결되어 있다면 -> 이미 연결되어 방문했는지 확인하고 (visited [1] = 0 인지) 확인하고 -> 그 이전까지 확인한 적이 없다면 -> st = []에 1번을 추가해서 -> 1번 그래프에서 연결된 정점들을 다시 탐색한다.

만약 1번 정점에서 -> 0번이 연결된 것을 확인하더라도 -> visited[0] = 1이라서 이미 방문했기 때문에 탐색 대상에 추가되지 않는다.

 

def dfs(computers, visited, start):
    st = [start]
    while st:
        i = st.pop()
        if visited[i] == 0:
            visited[i] = 1      
        for j in range(len(computers)):
            if computers[i][j] == 1 and visited[j]==0:
                st.append(j)

def solution(n, computers):
    answer=0
    visited = [0] * n
    
    for idx in range(0, n):
        if visited[idx] == 0:
            dfs(computers, visited, idx)
            answer += 1
    return answer