[Algorithm] 프로그래머스 43162 : 네트워크

문제
https://school.programmers.co.kr/learn/courses/30/lessons/43162
풀이
https://github.com/nowChae/algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/Lv.3/43162.%E2%80%85%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC.py

DFS와 BFS를 사용하는 뼈대 문제였다. 네트워크 유형 문제와 입력받은 리스트의 형태가 그래프를 나타나는 것으로 판단하고 빠르게 DFS와 BFS를 떠올린다면 금방 풀 수 있는 문제인 것 같다.

DFS와 BFS 모두 그래프 탐색 알고리즘이기 때문에 어떤 방법을 사용해도 정답은 나온다. 하지만 어떤 상황에서 어떤 탐색 방법을 사용할 지 모르니 되도록 두 가지 방법 모두 구현하고자 했다.

기본적인 dfs, bfs 함수를 만들어주고, 그래프의 개수를 판단하기 위해서 visited 리스트가 모두 true가 될 때까지 반복하도록 해주었다. 하나의 그래프는 result에 담기게 되고, result의 길이가 0인 경우는 그래프가 아니므로 result의 길이가 0보다 큰 경우에 answer의 값을 1 증가시켰다.

< 풀이 코드 >

from collections import deque

def dfs(start, graph, visited, result): #재귀
    visited[start] = True
    result.append(start)
    for i in range(len(visited)):
        if (not visited[i]) and (graph[start][i]):
            dfs(i, graph, visited,result)
            
def bfs(start, graph, visited, result): #큐
    queue = deque([start])
    visited[start] = True
    result.append(start)
    
    while queue:
        v = queue.popleft()
        result.append(v)
        for i in range(len(visited)):
            if (not visited[i]) and (graph[v][i]):
                queue.append(i)
                visited[i] = True
                
    

def solution(n, computers):
    visited = [False] * n
    answer = 0
    
    for i in range(n):
        result = []
        if not visited[i]: 
            dfs(i, computers, visited, result)
        if result:
            answer+= 1
    
    """
    for i in range(n):
        result = []
        if not visited[i]: 
            bfs(i, computers, visited, result)
        if result:
            answer+= 1
    """
    return answer