[구름톤 챌린지 #16] 연합

문제16. 연합

구름LEVEL

---

---

문제 해결 방법

오늘 문제는 유향 그래프에 대한 탐색을 할 수 있는지를 보는 문제이다. 무향 그래프와 유향 그래프는 사실 크게 다르지 않다. 인접행렬 기준으로 설명하자면, 무향 그래프는 array[start_node][end_node]와 array[end_node][start_node]가 같은 값을 가졌고, 어떻게 접근해도 똑같은 결과를 얻었다. 반면에 유향 그래프는 array[start_node][end_node]와 array[end_node][start_node]가 다를 수 있다. 따라서 start_node에서 end_node로 향하는 edge가 있는지를 array[start_node][end_node] 만을 이용해 접근해야한다. 이를 제외하고는 무향 그래프와 같다.

 

위 내용을 숙지한 상태에서 문제를 풀어보면, 시작 노드로부터 서로 양방향 연결되어있는 노드들의 개수를 구하는 문제이다. 바로 DFS와 BFS가 떠오른다. 오늘은 DFS로 문제를 풀어보도록 하자. 우선 DFS를 적용하기 가장 쉬운 방법은 재귀를 이용하는 것이다.

특정 노드가 현재 노드와 양방향 간선으로 이어져있는지 확인하고, 그렇다면 재귀를 이용해 그 노드와 양방향 간선으로 이어져있는 다른 노드가 있는지를 체크하는 방식으로 문제를 해결할 수 있다. 재귀함수를 이용한 코드는 아래와 같다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

arr = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
    s,e = map(int, sys.stdin.readline().split())
    arr[s][e] = 1

#재귀로 풀때
def dfs(i):
    global arr, visited

    for j in range(1,n+1):
        if j in visited:
            continue
        if arr[i][j] == 1 and arr[j][i] == 1:
            visited.add(j)
            dfs(j)

visited = set()
count = 0

for i in range(1,n+1):
    if i in visited:
        continue

    count += 1
    visited.add(i)

    #재귀로 풀때
    dfs(i)

print(count)

그런데 위처럼 재귀를 이용해 문제를 풀면, 항상 recursion error가 날지 걱정하게된다. DFS를 재귀가 아닌 방식으로 푸는 방법은 바로 스택을 이용하는 방법이다.

 

시작 노드에서 양방향으로 이어져있는 노드를 모두 스택에 넣는다. 그 다음, 스택에서 하나씩 꺼내서 반복한다. 이렇게 되면 나중에 스택에 들어간 노드부터 꺼내지기 때문에, 결과적으로 깊이 우선 탐색이 이루어지게 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

arr = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(m):
    s,e = map(int, sys.stdin.readline().split())
    arr[s][e] = 1

visited = set()
count = 0
dq = deque()

for i in range(1,n+1):
    if i in visited:
        continue

    count += 1
    visited.add(i)

    #재귀함수 대신 스택을 활용하는 법
    dq.append(i)
    while dq:
        popped_index= dq.pop()
        for j in range(1, n+1):
            if j in visited:
                continue
            if arr[popped_index][j] == 1 and arr[j][popped_index] == 1:
                visited.add(j)
                dq.append(j)

print(count)