프로그래머스 네트워크

DFS문제는 BFS로도 가능하니 둘다 풀어보자.

// DFS로 구현 1

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for com in range(n):
        if visited[com] == False:
            DFS(n, computers, com, visited)
            answer += 1 #DFS로 컴퓨터들을 최대한으로 방문하고 빠져나오면 하나의 네트워크.
    return answer

def DFS(n, computers, com, visited):
    visited[com] = True
    for connect in range(n):
        if connect != com and computers[com][connect] == 1: #연결되어진 컴퓨터
            if visited[connect] == False:
                DFS(n, computers, connect, visited)
                
                
                
// DFS로 구현 2      
def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]
    for node in range(n):
        # 노드 방문 전
        # 이전 반복문에서 방문한 적이 없었다면,
        # 이전 노드와 연결되어있지 않음. 서로 다른 네트워크
        if visited[node] == False:
            dfs(n, computers, node, visited)
            answer += 1

    return answer


# dfs 에서 하는 일을 바라보자
def dfs(n, computers, node, visited):
    visited[node] = True
    for connect in range(n):
        # 연결 여부 확인(자기 자신이 아니고, 연결되어 있는 경우)
        if connect != node and computers[node][connect] == 1:
            # 방문한 적이 없는 노드라면
            if visited[connect] == False:
                dfs(n, computers, connect, visited)

// BFS로 구현

def bfs_sol(n, computers):
    answer = 0

    visited = [False for _ in range(n)]
    queue = deque()
    for node in range(n):
        if visited[node] == False:  # node 가 방문한 적이 없으면
            queue.append(node)  # queue에 추가한 뒤, 확인 들어가자.
            while queue:
                cur_node = queue.pop()
                visited[cur_node] = True  # 방문 처리
                for tmp_node in range(n):
                    #  현재 노드와 상대 노드가 연결 처리된 경우
                    #  상대 노드를 확인해봐야함. -> queue에 추가해서 돌리자.
                    if cur_node != tmp_node and computers[cur_node][tmp_node] == 1:  
                        if visited[tmp_node] == False:
                            queue.append(tmp_node)

            answer += 1
        else:
            # 방문한 적이 있다?
            # 이전 노드에서 방문처리가 되었으므로 연결이 되어 있음
            continue

    return answer

 

 

 

참고 : 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

프로그래머스 - 네트워크 (DFS, BFS) Python

https://chul2-ing.tistory.com/31

[프로그래머스][DFS][BFS] - 네트워크 파이썬