그래프 알고리즘 코드 정리 [1: 기본 탐색(traversal)]

그래프 이론은 방대하다. 기본적으로 방문, 최단거리, DAG, 사이클, MST가 있고, 고급 알고리즘으로는 SCC, 경로, flow 등이 있다. 트리도 그래프의 일종이나 그 특성상 더 적합한 알고리즘이 있기도 하므로 별도로 다루게 된다. 이번 시간에 다룰 문제는 다음과 같다.

• Connected Components
• Topological Sort
• Bipartite or Cycle Check
• Shortest Path (BFS)

Graph traversal 문제 중에서 더 어려운 Strongly Connected Components, Articulation Points/Bridges, Flood Fill은 몇 차례에 나누어 다루기로 하겠으며, MST, SSSP, APSP, Special Graph (최단/장 거리, DP, Tree 등) 문제도 별도의 글로 추후에 다루겠다. 어려운 기법으로 이야기되는 DP는 하나의 풀이 방식이기에 기본 개념을 터득하고 나면 그다음부터는 문제마다 이를 적용하면서 다양한 사례에 기본 스킬을 계속 확장해 나가는 반면, 그래프는 배워야 할 이론도 방대하기에 여러 차례에 걸쳐 다양한 코드와 문제를 소개하고자 한다.

방문

DFS

DFS, depth-first search는 각 점에서 시작하여 인접한 노드 중 미방문 점에 대해 방문하되, 한 번 어떤 노드에 방문하면 일단 인접한 노드를 방문하는 함수를 계속 호출하면서 끝까지 방문을 하게 된다. 전체 노드가 한 덩어리의 graph를 이루고 있다면 특정 점에서만 DFS를 하면 되지만, 우리는 그렇다는 보장이 없는 한 forest (tree가 여러개 모인 집합) 라고 가정하고, 모든 점에서 dfs를 시도해야 한다.

아래 코드에서는, 미방문점 여부를 visited 배열을 통해 체크한다. 모든 점을 dfs 시작 전에는 미방문 상태(False)로 초기화 하고, dfs 함수 내부에서 방문시 값을 업데이트(True)한다.

 

 

import collections
n, m = map(int, input().split())  # number of vertices
adj = collections.defaultdict(list)
for _ in range(m):  # (unweighted, undirected) edges
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
visited = [False for _ in range(n)]

def dfs(u):
    global visited    # to make it writable
    visited[u] = True
    for v in adj[u]:  # adj is read-only
        if not visited[v]:
            dfs(v)
           
for i in range(n):
    if not visited[i]:
        dfs(i)

print(visited)

백트래킹과 DFS의 차이

백트래킹은 방문된 정점에 대해 방문기록을 다시 초기화하여, 다른 branch가 다시 방문할 수 있도록 하는 등, 모든 가능한 경로를 탐색하도록 하지만, DFS는 한 번 방문한 정점은 다시 방문하지 않는다.

DFS 응용

• 무방향 그래프의 Connected Components를 구할 수 있다. DFS는 방문을 시작하면 연결점은 모두 방문해 버리기 때문에, vertex를 돌아다니면서 미방문점(unvisited vertex)인 경우 DFS를 하고, DFS를 시작할 때 카운트를 하면 Connected Components의 개수를 구할 수 있다. 아래 코드에서는, 후술할 cycle check 문제와 유사하게 visited 값을 -1, -2와 같은 정수로 정했다. 각 노드에 여러 상태를 부여해서 원하는 목적을 달성할 수 있다.

'''
INPUT:
5 3
1 2
1 3
4 5

OUTPUT:
CC 1 :  1 2 3 
CC 2 :  4 5 
'''

import collections
n, m = map(int, input().split())  # number of vertices
adj = collections.defaultdict(list)
for _ in range(m):  # (unweighted, undirected) edges
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
visited = [-1 for _ in range(n)]  # -1: UNVISITED, -2: VISITED
numCC = 0  # ADDED for Connected Comps

def dfs(u):
    global visited    # to make it writable
    global numCC
    visited[u] = -2
    print(u+1, end=' ')  # ADDED to print vertices within a Connected Comp
    for v in adj[u]:  # adj is read-only
        if visited[v] == -1:
            dfs(v)

for i in range(n):
    if visited[i] == -1:
        numCC += 1  # ADDED for Connected Comps
        print("CC", numCC, ': ', end=' ')
        dfs(i)
        print()     # new line

• Topological sort of DAG (directed acyclic graph). Acyclic 체크, 맞다면 Topo sort 수행. Kahn's Algorithm은 생략.

'''
INPUT:
5 4
1 2
1 3
3 4
4 5

OUTPUT:
1 3 4 5 2

INPUT:
8 8
1 2
2 4
4 5
1 3
2 3
3 4
3 6
8 7

OUTPUT:
8 7 1 2 3 6 4 5
'''

import collections
n, m = map(int, input().split())  # number of vertices
adj = collections.defaultdict(list)
for _ in range(m):  # (unweighted, undirected) edges
    u, v = map(int, input().split())
    adj[u-1].append(v-1)   # must be directed, so DON'T make it double arraw
visited = [-1 for _ in range(n)]  # -1: UNVISITED, -2: VISITED
ts = []

def toposort(u):
    global visited, ts    # to make it writable
    visited[u] = -2       # VISITED
    #print(u+1, end=' ')   # ADDED to print vertices visiting
    for v in adj[u]:      # adj is read-only
        if visited[v] == -1:   # UNVISITED
            toposort(v)
    ts.append(u)          # ADDED for TOPOSORT

for i in range(n):
    if visited[i] == -1:  # UNVISITED
        toposort(i)

for v in reversed(ts):
    print(v+1, end=' ')

• 방향 그래프의 Cycle check

# edge cycle, CP4 4.2.8
'''
Input:  # directed graph
5 6
0 1
1 2
2 3
3 1
3 4
4 3
'''
import collections
adj = collections.defaultdict(list)
n, m = map(int, input().split())
for _ in range(m):
    u, v = map(int, input().split())
    adj[u].append(v)
dparent = [-1 for _ in range(n)]
dvisit = [-1 for _ in range(n)]
def dfs(u):
    dvisit[u] = -2  # EXPLORED
    for v in adj[u]:
        print(f"Edge {u} -> {v} is a ", end="")
        if dvisit[v] == -1:  # UNVISITED
            print("Tree edge\n")
            dparent[v] = u
            dfs(v)
        elif dvisit[v] == -2: # EXPLORED
            if v == dparent[u]:  ## corrected my misconception here
                print("Bidirectional edge\n")
            else:
                print("Back edge (Cycle)\n")
        elif dvisit[v] == -3:  # VISITED
            print("Forward/Cross edge\n")
    dvisit[u] = -3  # VISITED
for i in range(n):
    if dvisit[i] == -1:
        dfs(i)

BFS

BFS는 시작점으로부터 다른 정점까지의 최단거리(single source shortest path, SSSP)를(unweighted graph에 대해) 구하는데 활용할 수 있다.

'''
INPUT:
5 4
1 2
1 3
3 4
4 5

OUTPUT:
[0, 1, 1, 2, 3]
'''

import collections
n, m = map(int, input().split())  # number of vertices
adj = collections.defaultdict(list)
for _ in range(m):  # (unweighted, undirected) edges
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
dist = [0] + [float('inf') for _ in range(n-1)]  # dist from source(0)

q = collections.deque()
q.append(0)

while q:
    u = q.popleft()
    for v in adj[u]:
        if dist[v] != float('inf'):   # visited, skip
            continue
        dist[v] = dist[u] + 1    # all weights are assumed to be 1
        q.append(v)

print(dist)

BFS 응용

• Bipartiteness/cycle를 확인. Two color 문제와 같으며,  DFS로도 가능. 아래는, two color를 인접한 경우에 다르게 칠할 수 있는 연결상태라면 그 칠한 색상을 출력하고, 불가능하면 IMPOSSIBLE 출력. https://cses.fi/problemset/task/1668/
  
  • 이 문제를 풀기 위해서, 각 노드별 색상 및 방문여부를 나타내는 array인 color를 만들고, 기초값을 미방문(inf)으로 하고 노드를 다니면서 미방문점에 대해서 초기 색상을 임의로 부여한 다음, 거기서부터 탐색(BFS/DFS)을 한다. 탐색시에는 시작점의 컬러값을 가져와서 이 값을 추후 탐색 노드에 대해서 뒤집어 부여하면서 탐색을 개시하는 방식으로 한다. 
  • 컬러를 미리 시작점에서부터 부여해야 하는 것은 이 문제의 속성상 필요하다. 맨 처음 BFS 함수를 각 미방문점에 대해 호출할 때 해당 점에 대해 색을 부여했으므로, BFS 함수 내에서 다시 추후 탐색을 실시할 때에도 역시 피방문점에 대해 색을 부여해야 하는 것이다.
  • 만일 탐색중에 현재 점과 탐색대상 점(=미방문점)의 색이 같다면 cycle이 있는 것이고, 따라서 bipartite가 불가능하다.

CSES - Building Teams

'''
INPUT:
5 5
1 2
1 3
3 2
3 4
4 5

OUTPUT:
IMPOSSIBLE

INPUT:
5 3
1 2
1 3
4 5

OUTPUT:
1 2 2 1 2 
'''

import collections
n, m = map(int, input().split())  # number of vertices
adj = collections.defaultdict(list)
for _ in range(m):                # (unweighted, undirected) edges
    u, v = map(int, input().split())
    adj[u-1].append(v-1)
    adj[v-1].append(u-1)
color=[float('inf') for _ in range(n)]
# ADD: when source is fixed, s=0; color[s]=0;
isBipartite = True    # Null Hypothesis

q = collections.deque()

def BFS(s):
    global q, isBipartite
    q.append(s)
    while q and isBipartite:
        u = q.popleft()
        for v in adj[u]:                   # adj is read-only
            if color[v] == float('inf'):   # UNvisited
                color[v] = 1 - color[u]    # flip color (can also do XOR ^)
                q.append(v)
            elif color[v] == color[u]:     # VISITED but same color as mine
                isBipartite = False
                break

for i in range(n):
    if color[i] == float('inf'):    # visit all UNVISITED source vertex
        color[i] = 0
        BFS(i)

if not isBipartite:
    print('IMPOSSIBLE')
else:
    for v in color:
        print(v+1, end=' ')

 

참고문헌
Laaksonen, "Guide to Competitive Programming", 2ed, 2020
Halim et al., "Competitive Programming (Book 1)", 4ed, 2020