ps:2색_색칠
2색 색칠
- 인접한 두 노드는 다른 색을 갖도록 하면서, 전체 노드들을 2가지 색으로 색칠하기.
- 일반적인 vertex k-coloring 은 NP라서 PS에서는 다룰일이 별로 없다.
기본정리
- 2색 색칠이 가능하다 ⇔ 이분그래프이다
- 그래프에 홀수길이 사이클이 없으면 2색 색칠 가능
- 트리는 사이클이 아예 없으니 당연히 가능
알고리즘
- 기본적으로는 그래프를 순회하면서 컬러를 지정하면 된다. 시간복잡도는 O(V+E)
- Disjoint Set을 사용하는 방법도 가능하긴 하다.
- BFS에 비해 느리다.
- 하지만, incremental 하게 관리해야 할 필요가 있는 경우에는 이 방법이 필요하다
- 코드는 A Bug’s Life 참고
- 2-SAT으로 모델링해서 푸는 방법도 가능하다.
- 이건 disjoint set을 쓰는것보다도 더욱 느릴것 같기는 하다.
- 하지만 문제에 변형이 복잡하게 주어지면, 이렇게 모델링하는게 간단할수도 있을것 같긴 하다 (아직 본적은 없다)
구현
- 보통은 2-colorable 한지(=이분그래프인지) 여부를 찾는 태스크가 실제 coloring을 요구하는 태스크보다 더 흔하기는 하다. 그래서 is_bipartite 와 같은 함수를 따로 만드는 것도 생각해봤지만, 기각.
- 방문처리를 color를 주는것으로 처리하기 때문에, DFS나 BFS나 코드가 stack을 쓰느냐 queue를 쓰느냐를 제외하고는 그냥 똑같다. 속도는 BFS가 살짝 더 빨랐다.
- DFS는 이런식
def two_coloring(graph): color = [None] * len(graph) for source in range(len(graph)): if color[source] is not None: continue stack = [source] color[source] = True while stack: u = stack.pop() color_u = color[u] for v in graph[u]: if color[v] is None: color[v] = not color_u stack.append(v) elif color[v] == color_u: raise ValueError('Not bipartite graph') return color
- BFS는 이런식
def two_coloring(graph: Graph) -> list[bool]: color = [None] * len(graph) for source in range(len(graph)): if color[source] is not None: continue color[source] = True queue = collections.deque([source]) while queue: u = queue.popleft() col_u = color[u] for v in graph[u]: if color[v] is None: color[v] = not col_u queue.append(v) elif color[v] == col_u: raise ValueError( 'Graph is not 2-colorable (not bipartite).' ) return color
코드
관련 문제
- 이분 그래프: N≤20,000, M≤200,000
- 적의 적: N≤2,000, M≤1,000,000
- A Bug’s Life: N≤2,000, M≤1,000,000
ps/2색_색칠.txt · 마지막으로 수정됨: 2023/04/04 15:05 저자 teferi
토론