그래프 연결성 판정

한 점(node 1)에서 시작하여 연결된 노드를 방문할 때 방문이 되지 않는 점을 찾는 것을 하고자 한다. 문제는 다음에서 가져왔다.

https://open.kattis.com/problems/wheresmyinternet

Where's My Internet?? – Kattis, Kattis

DFS

가장 간단한 탐색 방법으로 스택을 사용하는 DFS를 써보았다. 케이스에 따라서 sys.setrecursionlimit을 설정하지 않으면 RTE가 나오기도 한다. 스택은 후입선출(LIFO) 방식이다. 기본적인 얘기지만 헷갈리면 반대로 말할 수 있는 위험이 늘 있다. 그러므로 면접 등에서도 한 번 생각해 보고 제대로 말해야 하겠다.

참고로, 통상 dfs에 argument로 방문여부를 나타내는 visited를 넣지만, c++ 에서 처럼 dfs 함수 내에서 main 함수에 정의된 값에 액세스 하여 그 값을 변화시킬 수 있으려면 함수 내에서 global 선언을 한 번 해주면 된다.

import collections
import sys
sys.setrecursionlimit(10**6)

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)

dfs(0)

isConnected = True
for i in range(n):
    if not visited[i]:
        print(i+1)
        isConnected = False

if isConnected:
    print("Connected")

BFS

조금 구현이 어렵다고 여겨지는 탐색방법이 BFS이다. 하지만 DFS는 스택 오버플로우 우려나 Python의 스택 호출과 관리에 시스템 자원을 많이 활용하는 문제로 속도가 약간 느릴 수 있어, BFS를 비교해본다.

BFS는 선입선출(FIFO)의 queue 구조를 사용한다. 이를 구현한 라이브러리로 collections의 deque를 썼다. list처럼 append로 노드 번호를 추가하고, popleft로 뺀다. 뺀 것에 방문여부를 참으로 표시하고, 인접 노드를 queue에 추가한다. 이를 queue에 원소가 있는 동안 수행한다. 인접노드가 없는 상황이 되면 for문이 돌지 않게 되고 while문도 거기서 종료된다.

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)]

### differs here
q = collections.deque([0])
while q:
    u = q.popleft()
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            q.append(v)
###

isConnected = True
for i in range(n):
    if not visited[i]:
        print(i+1)
        isConnected = False

if isConnected:
    print("Connected")

Union Find

이 구조로도 풀 수 있겠으나 코테 목적이라면 해당 자료구조를 구현하고 시작해야 하는 방식으로 문제를 푸는 것은 체력 안배에 좋은 것 같지는 않다.  MST를 Kruskal로 풀 때 쓰도록 하는 것이 좋다고 생각된다.

속도비교

맨 위가 DFS, 다음이 BFS이다. 속도를 비교해 보니 BFS가 약간 빨랐다.