문제 개요
무방향 그래프가 하나 주어졌을 때, 이 그래프가 크기가 l인 독립 집합(independent set)을 포함하는지 확인해야 합니다. 크기 l의 독립 집합이 하나라도 존재하면 Yes를, 존재하지 않으면 No를 반환하면 됩니다.
여기서 그래프의 독립 집합이란 서로 직접 연결되어 있지 않은 정점(vertex)들의 집합을 의미한다는 점을 기억해야 합니다. 즉, 집합 안의 어떤 두 정점 사이에도 간선이 존재하지 않아야 합니다.
예를 들어 입력이 다음과 같고 L = 4라고 가정해 보겠습니다.
이 경우 출력은 Yes가 됩니다.
접근 방법: 백트래킹
이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 각 정점에 대해 '현재 집합에 포함하는 경우'와 '포함하지 않는 경우'를 재귀적으로 탐색하면서, 선택된 정점들이 서로 인접하지 않는지 계속 검증하는 것입니다.
구체적인 풀이 단계는 다음과 같습니다.
- is_valid(graph, arr) 함수 정의: 선택된 정점 목록 arr가 유효한 독립 집합인지 검사합니다.
- i를 0부터 arr의 크기까지 순회합니다.
- j를 i + 1부터 arr의 크기까지 순회합니다.
- graph[arr[i]][arr[j]]의 값이 1이면(두 정점이 인접하면) False를 반환합니다.
- 모든 쌍이 인접하지 않으면 True를 반환합니다.
- solve(graph, arr, k, index, sol) 함수 정의: 백트래킹으로 독립 집합을 탐색합니다.
- k가 0이면(즉, k개의 정점을 모두 선택했다면) is_valid()로 유효성을 검사하고, 유효하다면 sol[0]을 True로 설정한 뒤 종료합니다.
- k가 0이 아니면서 index >= k인 경우, 현재 index를 집합에 포함하는 경우와 포함하지 않는 경우 두 갈래를 모두 재귀적으로 탐색합니다.
- index < k인 경우, 남은 정점 수가 부족하므로 현재 index를 반드시 포함하는 경우만 탐색합니다.
예제 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
def is_valid(graph, arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if graph[arr[i]][arr[j]] == 1:
return False
return True
def solve(graph, arr, k, index, sol):
if k == 0:
if is_valid(graph, arr) == True:
sol[0] = True
return
else:
if index >= k:
return (solve(graph, arr[:] + [index], k-1, index-1, sol) or solve(graph, arr[:], k, index-1, sol))
else:
return solve(graph, arr[:] + [index], k-1, index-1, sol)
graph = [
[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 1, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 1]]
k = 4
arr = []
sol = [False]
solve(graph, arr[:], k, len(graph)-1, sol)
if sol[0]:
print("Yes")
else:
print("No")입력
[[1, 1, 0, 0, 0], [1, 1, 1, 1, 1], [0, 1, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 1]], 4
출력
Yes
코드 설명 및 복잡도
그래프는 인접 행렬(adjacency matrix) 형태로 표현되며, graph[i][j]가 1이면 정점 i와 j 사이에 간선이 있다는 뜻입니다. 위 예제에서 정점 0, 2, 3, 4는 서로 인접하지 않으므로 크기 4의 독립 집합이 존재하여 Yes가 출력됩니다.
is_valid() 함수는 선택된 정점들의 모든 쌍을 비교하므로 O(k²) 시간이 걸리며, solve() 함수는 각 정점마다 포함/제외 두 가지 선택지를 탐색하므로 최악의 경우 지수 시간 복잡도를 가집니다. 이는 독립 집합 문제가 NP-난(NP-hard) 문제이기 때문으로, 작은 크기의 그래프에는 백트래킹이 실용적인 접근 방식입니다.