[프로그래머스 DFS/BFS]네트워크 - Python3

문제

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

코딩테스트 연습 - 네트워크 | 프로그래머스

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

입출력

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1

 

알고리즘

이 문제는 DFS, BFS 두 가지 방법을 모두 사용해서 풀 수 있다. 방문하지 않는 노드가 없을 때까지  DFS나 BFS를 사용해서 노드를 순회하고, 이때  DFS나 BFS를 할때마다 answer의 값을1 증가시켰다. 일단 올려놓은 코드는 BFS, DFS(반복), DFS(재귀)순이니, 하나하나 보면서 설명하겠다. 

설명1

"""
bfs를 활용해서 푼 코드
"""

def bfs_solution(n, computers):
    visited = [-1] * n
    answer = 0

    for i in range(len(visited)):
        if visited[i] == -1:
            answer += 1
            start = i
            queue = [start]
            visited[start] = 1
            print(start, "방문")

            while queue:
                temp = queue.pop(0)
                for j in range(len(computers[temp])):
                    if temp == j:
                        print(temp, j, "자기 자신과의 연결")
                    elif visited[j] == 1:
                        print(temp, j, "이미 방문한 노드")
                    elif computers[temp][j] == 0:
                        print(temp, j, "연결 안된 노드")
                    else:
                        visited[j] = 1
                        queue.append(j)
                        print(start, j, "방문")
                        print("queue: ", queue)
                print(temp, "bfs한 결과 vistied: ", visited)
                print("---", temp, "bfs 끝---\n")

    return answer

visited 배열은 해당 노드가 방문이 되었는지 안되었는지에 대한 정보를 갖는 배열이다. 이 배열이 없다면, 우리는 한 노드를 계속 중복 방문하게 될 것이다. visited의 값을 노드의 갯수만큼의 -1로 초기화한다. 

1. visited배열을 순회하면서, 방문하지 않은 노드가 있을 경우(visited[i]가 -1인 원소가 있을 경우)만 반복을 실행한다.
   1. 어떤 노드가 아직 방문되지 않았다면, 그 노드부터 bfs를 실행할 것이다. 결과인 answer는 bfs를 실행한 횟수와 동일한 값이므로, answer의 값을 1 증가시킨다. 
   2. queue에 시작점(start)을 넣어서 선언한다(bfs는 선입선출의 큐 구조를 활용한다).
   3. temp노드를 방문했다고 표시한다. 즉, visited[temp]의 값을 1로 바꾼다. 
   4. 그리고 queue에 값이 있는 동안, 즉 temp노드에서 갈 수 있는 노드가 있는 동안 다음을 반복한다
      1. queue에서 값을 하나 pop 한 뒤 temp에 저장한다
      2. computers[start]를 순회하면서, start노드에서 갈 수 있는 노드를 탐색한다. computers배열은 그래프의 인접행렬의 형태이다. 
      3. 자기 자신과의 연결이 아니고, 이미 방문한 노드가 아니고, 연결이 안된 노드가 아니라면, 그 노드는 start에서 한번에 갈 수 있는 노드이므로, 해당 노드를 나타내는 j를 방문했다고 하기 위해 vistied[j]를 1로 바꾸고, 다음에 j에서 BFS를 하기 위해 queue에 j를 append한다.
2. answer를 리턴한다. 

위의 코드는 사실 디버깅이나 결과 확인을 위해 print문을 많이 썼다. 초심자라면 위 코드 그대로 따라서 실행시켜보면, bfs가 어떻게 진행되는지 알 수 있으니 참고 바란다. 개고수면 여기 들어오지도 않았겠지 ㅎㅎ~

 

설명2

아래 코드는 반복적 DFS를 활용해서 푼 코드이다. 

"""
dfs를 반복적으로 구현해서 푼 코드
"""
def dfs_iterative_solution(n, computers):
    visited = [-1] * n
    visit_order = []
    answer = 0
    nodes = range(n)

    for i in range(len(visited)):
        if visited[i] == -1:
            answer += 1
            start = i
            stack = [start]
            visited[start] = 1
            print(start, "방문")
            visit_order.append(start)

            while stack:
                temp = stack.pop()
                for j in range(len(computers[temp])):
                    if temp == j:
                        print(temp, j, "자기 자신과의 연결")
                    elif visited[j] == 1:
                        print(temp, j, "이미 방문한 노드")
                    elif computers[temp][j] == 0:
                        print(temp, j, "연결 안된 노드")
                    else:
                        visited[j] = 1
                        stack.append(j)
                        visit_order.append(j)
                        print(start, j, "방문")
                        print("stack: ", stack)

    print("방문 순서: ", visit_order)
    return answer

BFS와 상당히 유사한데, 차이점은 큐를 쓰느냐 스택을 쓰느냐 뿐이다. 큐와 스택의 특징에 따라, 노드별로 방문 순서는 다르지만 결과는 같다. 

1. visited배열을 n개의 -1로 초기화한다.
2. BFS와 방문 순서의 차이를 알아보기 위해 visited_order도 선언했다. 한 노드를 처음 방문할 때마다 여기다가 append할 것이다. 
3. 인덱스 i가 visited를 순회하면서, 아직 방문하지 않은 노드가 있는 동안 반복한다
   
   1. 아직 방문하지 않은 노드가 있다면, answer를 1 증가시키고, start에 그 노드(i)를 할당한다.
   2. i를 방문했다는 표시를 하기 위해 visited[i]를 1로 바꾼다.
   3. 방문 순서를 알기 위해, visited_order에 start를 append한다.
   4. start노드를 담은 stack 배열을 선언한다. 
   5. stack에 원소가 있는동안, 다음을 반복한다
      1. stack에서 원소하나를 pop해서 temp에 저장한다. 이 때, pop되는 원소는 젤 뒤에 원소이다.
         1. 인덱스 j가 computers[temp]를 순회하면서, 갈 수 있는 노드를 찾는다. 자기 자신과의 연결이 아니고, 이미 방문한 노드가 아니고, 연결 안된 노드가 아니라면, 그 노드 j 를 방문한다(visited[j] = 1로 한다). 
         2. stack에 노드 j를 append한다.
4. answer 를 리턴한다. 

 

설명3

아래 코드는 dfs를 재귀적으로 구현한 코드이다. 

"""
dfs를 재귀적으로 구현해서 푼 코드
"""

answer = 0

def recursion(n, computers, visited, start):
    global answer
    visited[start] = 1
    print(start, "방문")

    for i in range(len(computers[start])):
        if computers[start][i] == 1 and start != i and visited[i] == -1:
            recursion(n, computers, visited, i)
    return


def dfs_recursive_solution(n, computers):
    global answer
    visited = [-1] * n

    for i in range(0, n):
        if visited[i] == -1:
            print("main함수 반복,", i, "에서 dfs 시작")
            answer += 1
            recursion(n, computers, visited, i)
    print("main함수 반복 끝\n")
    return answer

일단, 재귀함수의 구성을 설명하겠다. 재귀함수 recursion()는 컴퓨터의 갯수 n, 연결상태인 computers, 방문 여부를 가진 visited, 시작점인 노드 start를 파라미터로 받는다. 그리고, 더 갈 수 있는 노드가 있는 경우, 그 노드를 인덱스로 줘서 재귀호출을 한다. 더 갈수 있는 노드가 없다면, 중지한다. 

메인함수는 다른 답안과 마찬가지로 visited를 초기화하고, 인덱스 i를 이용해 0부터 visited[n-1]까지 순회하면서, 아직 방문되지 않은 노드가 있다면 그 노드에서 dfs를 실행하고 answer를 1 증가시킨다.

이렇게만 써놓으면 사실 다른 쓸말이 없다.  그렇기도 하고, 이 문제는 아주 심혈을 기울여서 푼 문제이기 때문에, 메모리 스택을 통해 살펴보도록 하자. 

위의 그림에서는 노드 번호는 1, 2, 3이지만, 코드상에서는 0, 1, 2로 간주한다. 

노드가 몇개 없다보니, 메모리 스택을 봐도 뭐가 어찌되는지 잘 모르겠다. 아래 코드 결과 화면을 더 참고하자.

결과

BFS 실행 결과

 

반복적 DFS 실행 결과

 

재귀적 DFS 실행 결과

 

이는 올바른 결과이다. 코드와 결과화면을 참조하면, DFS와 BFS가 어떻게 돌아가는지 대충 그 흐름을 알 수 있다.

후기

이 문제를 풀 수 있는 3가지 방법으로 모두 풀어보았다. 깊이우선탐색(재귀/반복), 너비우선탐색 이 두 가지는 둘 다 중요한 개념이므로 꼭 이해해야 한다.

옛날에 이문제풀다가 포기했었는데, 풀리니까 기분 넘좋다. 성장하는 섹시한 개발자, 줄여서 성섹자라 할 수 있겟다.