DFS, BFS - 네트워크

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

프로그래머스

입출력 예시를 보면, 첫 번째 예시는 1번과 2번 컴퓨터만 연결되어 있고, 3번 컴퓨터는 아무와도 연결되지 않아서 아래와 같은 그림이다.

나는 지금까지 DFS, BFS를 사용하는 문제에서 모든 노드들이 연결되어 있는 형태의 그래프만 봐왔다. 

그런데 이 문제에서는 이 예시처럼 모든 컴퓨터들이 연결되있는 것이 아니기 때문에, 상황에 따라 탐색을 여러번 해야한다고 생각했다.

 

아래 그림과 같이 컴퓨터들이 연결되어 있다고 가정해보자.

그러면 1번 컴퓨터부터 bfs를 시작할때 5번 컴퓨터까지만 탐색이 가능하고, 3번 컴퓨터부터 새로 탐색을 해야한다. 

그래서 내가 생각한 흐름은, 각각 모든 컴퓨터가 탐색을 시작하는 첫 번째 노드가 되고 탐색이 끝날때마다 이전노드에서 탐색을 했을때와 

다른 점이 있을 때마다 네트워크 개수를 하나씩 추가하는 것이다.

 

말로 설명하니까 여러운데,

일단 반복문을 통해 탐색 알고리즘을 n 번실행시킨다. 

제일 먼저 1번 컴퓨터부터 탐색을 하면, 1번 컴퓨터는 2번 컴퓨터와 연결되어 있고, 2번 컴퓨터는 5번 컴퓨터와 연결되어 있기 때문에 5번 컴퓨터까지만 탐색하고 더이상 탐색을 하지 않을 것이다. 그리고 1, 2, 5번 컴퓨터들은 하나의 네트워크를 이룬다.

그 다음으로는 2번 컴퓨터부터 탐색을 하는데, 2번 컴퓨터가 속한 네트워크는 1번 컴퓨터부터 탐색해서 알아낸 네트워크와 동일하기 때문에 패스한다. 

다음으로 3번 컴퓨터부터 탐색할때는, 3번 컴퓨터는 4번 컴퓨터랑만 연결되어 있어서 4번 컴퓨터까지 탐색하고 탐색을 멈출 것이고, 새로운 하나의 네트워크를 이룬다. 

이런식으로 탐색이 끝날때마다 새로운 네트워크가 생겼는지, 안생겼는지를 판단하면서 네트워크 개수를 세어 가면 되는 것이다.

그럼 다음으로 생각해 봐야할 부분이, 어떻게 새로운 네트워크인지 아닌지를 판단하냐는 것이다.

내가 생각한 방법은 다음과 같다.

dfs 이든 bfs 이든, 일반적으로 탐색할때 각 노드를 방문 했는지를 체크하는 visited 배열을 활용한다.

그래서 n번의 반복문에서 탐색이 끝날때마다 visited에서 True의 개수를 세고, 이 True 개수에 변화가 생길때마다 새로운 네트워크가 생겼다고 생각할 수 있는 것이다.

 

아까 위의 예시를 생각해보면, 

1번 컴퓨터부터 탐색을 하면 visited = [True, True, False, False, True] 가 될것이다.

그 다음 2번 컴퓨터부터 탐색할때도 visited는 동일하게 [True, True, False, False, True] 일 것이다. 왜냐하면 1번 컴퓨터와 같은 네트워크 이기 때문에 이미 1번 컴퓨터에서 시작한 탐색에서 모두 방문한 노드들이기 때문이다. 

하지만 3번 컴퓨터부터 탐색을 하게 되면, visited에 변화가 생긴다. visited = [True, True, True, True, True] 가 되는 것이다.

이런식으로 visited에 변화가 생겼을때, 네트워크 개수를 세어준다. 

 

그래서 내가 작성한 코드는 아래와 같다.

from collections import deque

def bfs(graph, v, visited):
    result = []
    queue = deque()
    queue.append(v)
    while queue:
        v = queue.popleft()
        if visited[v-1] == False:
            visited[v-1] = True
            result.append(v)
        for i in graph[v]:
            if visited[i-1] == False:
                queue.append(i)
    return visited

def solution(n, computers):
    answer = 0
    visited = [False] * n
    graph = [[] for _ in range(n+1)]
    for i in range(n):
        for j in range(n):
            if i != j and computers[i][j] == 1:
                graph[i+1].append(j+1)

    true_num = 0
    for i in range(1, n+1):
        bfs_result = bfs(graph, i, visited)
        if bfs_result.count(True) > true_num:
            true_num = bfs_result.count(True)
            answer += 1

    return answer

인풋으로 받는 computers 가 각 컴퓨터들의 연결 상태를 나타내긴 하지만, 이전에 내가 bfs 알고리즘에서 사용했던 그래프와는 형태가 달라서 익숙한 형태의 graph를 다시 만들어서 bfs 알고리즘에서 사용했다. 

그리고 solution 함수 안의 true_num은 visited에서 True의 개수를 기록하고 비교하기 위해 쓰인다.

반복문 안을 보면, n번 반복하면서 bfs를 계속 실행시키고 그때마다 기존의 true_num과 bfs 탐색의 결과로 나오는 visited에서 True의 개수를 비교해서 변화가 생기면 true_num은 값을 업데이트 해주고 answer를 1 추가해 주었다. 

 

이 코드로 답안 제출을 했을때 통과가 되긴 하지만, graph를 새로 만드는 부분을 생략해도 될것 같아서 좀 더 고민한 끝에 아래와 같이 코드를 수정했다. 

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [False] * n

    def bfs(v, visited):
        queue = deque()
        queue.append(v)
        visited[v] = True
        while queue:
            node = queue.popleft()
            for i in range(n):
                if computers[node][i] == 1 and visited[i] == False:
                    visited[i] = True
                    queue.append(i)
        return visited

    true_num = 0
    for i in range(n):
        bfs_result = bfs(i, visited)
        if bfs_result.count(True) > true_num:
            true_num = bfs_result.count(True)
            answer += 1

    return answer

인풋으로 받은 computers를 bfs 함수에 인자로 넘겨주지 않고도 사용할 수 있도록 bfs 함수를 solution 함수 내부로 옮겼다.

그리고 bfs 함수를 보면, graph를 사용하지 않기 때문에 for 반복문이 n번 반복하도록 바뀌었고, 반복문 안에서도 graph가 아닌 computers를 사용해서 해당 컴퓨터가 연결되어 있는지를 확인한다.

 

이 문제는 dfs와 bfs 둘다 풀이가 가능한 문제이고, 나는 bfs가 더 익숙하지 않다고 느껴져서 이번에는 bfs로 풀이를 진행했다.