[programmers] 네트워크

프로그래머스 Lv.3 네트워크

문제 분석
DFS/BFS 카테고리의 문제이다.

그림이 좀 허접하지만..
아무튼 연결된 컴퓨터 뭉치를 하나의 네트워크로 본다.
이때 총 네트워크가 몇 개 구성되는지 계산하는 문제이다.

접근 방법
DFS를 사용하기로 한다.
1. visited 배열을 선언함 (0 : 아직 구성 안됨, 1 : 구성 완료)
2. DFS함수를 선언함.

이 부분이 아이디어를 세우는 데 가장 어려웠다.
DFS함수를 어디서 언제 호출해야 할지가 헷갈렸다.
------------------------------------------------------------
1. visited가 0인 computer을 만나면 visited를 1로 바꿔주고
2. 다른 computer들에 대해 탐색을 진행한다.
3. 현재 computer의 index는 computer로 받는다.
4. computer와 다른 위치에 있는 index에 대해서
5. computers[computer] 배열이 1이면
   computer와 index는 같은 네트워크에 연결되어 있음.
6. 이때 해당 computer가 아직 네트워크 구성이 안된 상태라면
7. 해당 index의 computer를 기준으로 다시 DFS 재귀함수를 호출한다.
8. 재귀함수를 호출하다가 연결되지 않은 새로운 computer가 발견되면
9. answer++ 로 카운팅 해주고 다시 해당 computer에서 반복한다.
------------------------------------------------------------

작성한 코드

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

def DFS(n, computers, computer, visited):
    visited[computer] = 1
    for i in range(n):
        if i != computer:
            if computers[computer][i] == 1:
                if visited[i] == 0:
                    DFS(n, computers, i, visited)

이전에 풀었던 DFS 문제와 다르게,
solution 함수에서 DFS를 계속 호출해주어야 한다.
그 부분에서 한참 애를 먹었다.

일단 정답이 나왔다.
BFS로도 추가로 풀어보기로 했다.

BFS를 이용한 다른 풀이

def BFS(n, computers, computer, visited):
    queue = []
    queue.append(computer)
    while queue:
        computer = queue.pop()
        visited[computer] = 1
        for i in range(n):
            if i != computer:
                if computers[computer][i] == 1:
                    if visited[i] == 0:
                        queue.append(i)

가만 큐를 이렇게 선언해주면 안 됐나?
일단 큐에 computer index를 넣고
다시 큐에서 computer를 빼낼 때 visited를 1로 해줘야 한다.

이 문제는 DFS가 더 효율적인 문제였다.
거의 모든 점에서 효율적이다. 왜 그럴까?

이 문제는 컴퓨터의 수가 적고, 연결된 컴퓨터를 연쇄적으로 찾는 방법이기 때문에, 깊이 우선 탐색이 더 유리한 것 같다.
사실 컴퓨터 대수 제한이 200으로 낮아서 별 차이가 안 나는 것 같다.