[DFS/BFS] 네트워크 (프로그래머스, Level 3)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

• 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
• 쉽게 말하면, 네트워크는 서로 연결되지 않은 독립적인 노드 그룹의 개수이다.

예제 1)
아래 그림의 경우 총 2개의 네트워크가 존재한다.

예제 2)
아래의 경우 총 1개의 네트워크가 존재한다.

• 입출력 예
  

풀이

1번 노드부터 각 노드에서 연결되어 있는 모든 노드를 최대한 탐색한 후, 더 이상 연결된 노드가 없으면 탐색을 종료한다. 탐색을 종료하면 answer의 값을 1 증가시킨 후, 다음 노드에 연결된 노드들을 모두 탐색하는 동일한 과정을 진행한다. 더 이상 탐색할 노드가 없으면 알고리즘을 종료한 후 정답을 return 한다.

코드

• 처음 문제를 보고 생각했을 때는 DFS만 활용해서 풀 수 있는 문제라고 생각했다. 다른 사람들의 풀이를 참고해보니 해당 문제는 DFS 뿐만 아니라 BFS로도 풀이할 수 있었다.
• 두 가지 방법을 모두 사용해서 문제를 풀어보고자 한다.

DFS 코드

def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]     # 방문 여부 저장 배열
    
    for com in range(n):
        if visited[com] == False:   # 1번 ~ n번 컴퓨터까지 가면서 방문하지 않은 컴퓨터라면
            DFS(n, computers, com, visited)
            answer += 1
    return answer


def DFS(n, computers, com, visited):
    visited[com] = True        # 해당 노드의 방문 여부를 True로 변경
    for i in range(n):          # 해당 노드와 연결된 다음 노드들을 모두 탐색
        if i != com and computers[i][com] == 1 and visited[i] == False:    
                DFS(n, computers, i, visited)       # i랑 연결된 다음 노드도 쭉 탐색

# 자기 자신이 아니고, 이전 노드(com)와 현재 노드(i)가 연결된 노드이며, 현재 노드가 방문하지 않은 노드라면 방문하고, 현재 노드(i)에 대한 DFS를 계속 진행
# 연결되지 않은 노드가 나오는 순간 DFS 종료

BFS 코드

1)

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]
    
    for com in range(n):
        if visited[com] == False:
            BFS(n, computers, com, visited)
            answer += 1
    
    return answer

def BFS(n, computers, com, visited):
    visited[com] = True     # 방문을 했으므로 방문여부를 참으로 변경
    queue = deque()
    queue.append(com)
    
    while len(queue) > 0:       # 큐에 요소가 남아있는 동안 계속 append, pop 작업을 진행
        com = queue.pop()
        visited[com] = True
    
        for i in range(n):
            if visited[i] == False and computers[i][com] == 1 and i!=com:
                queue.append(i)

2) BFS 방식으로 풀이하였는데, BFS 내부 자체에서 재귀를 사용했다. 아래 방식보다는 위의 BFS 또는 DFS 방식으로 구현하면 좋을 것 같다.

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False for _ in range(n)]
    
    for com in range(n):
        if visited[com] == False:
            BFS(n, computers, com, visited)
            answer += 1
    
    return answer

def BFS(n, computers, com, visited):
    visited[com] = True     # 방문을 했으므로 방문여부를 참으로 변경
    queue = deque()
    queue.append(com)
    
    for i in range(n):
        if visited[i] == False and computers[i][com] == 1 and i!=com:
            BFS(n, computers, i, visited)

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