테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Knights of Round Table ======

===== 풀이 =====
  * [[ps:problems:boj:18282]]와 동일한 문제.
  * 연속한 3명이 같은 색깔이 되어서는 안된다는 조건을 그대로 활용해서 답을 찾으려면 만만치 않다. [[ps:twosat]] 으로 모델링하는것이 가능할지도 모르겠다.
  * 조건을 조금 변형해서, 1번과 2번, 3번과 4번, 5번과 6번, .. 이런식의 페어들이 같은 색깔이 되지 않아야 된다고 모델링해보자. 
  * 이 조건은 연속한 3명이 같은 색깔이 되지 않는다는 원래 조건보다 더 타이트한 조건이다. 즉, 이 조건을 만족하는 답을 찾으면, 원래 조건도 만족한다.
  * 이 조건을 만족하는 답을 찾는 것은 간단하다. 그래프를 만들고, 다른색이어야 하는 페어들에 대해서 엣지를 만든다. 문제에서 주어진 order들에 엣지를 만들고, 지금 말한대로 1-2, 3-4, ..., 이런 엣지들을 추가한다. 이제 이 그래프를 [[ps:2색 색칠]]하면 답을 찾을수 있다.
  * 신경쓰이는 점은, 우리가 변형한 조건이 처음 조건보다 더 타이트한 조건이기 때문에, 원래 조건을 만족하는 답이 있음에도 불구하고 이 조건을 만족하는 답이 없는 경우가 있을 수 있지 않을까 하는 걱정이다. 그러나 조금 생각해보면, 이 조건을 만족하는 답이 항상 존재한다는 것을 알수 있다. 2색 색칠이 불가능하려면, 홀수 사이클을 포함하고 있어야 한다. order에서 추가된 엣지들은 모두 disjoint하고, 그 뒤에 인접한 애들간에 추가된 엣지들도 disjoint 하다. 따라서, 사이클이 생긴다면, order엣지와 인접엣지가 번갈아가면서 나오는 형태일수 밖에 없고, 그렇다면 사이클의 크기는 항상 짝수일수밖에 없다.
  * 그래프에 엣지를 추가하는데에 O(V), 사이클 체크에 O(V+E)인데.. 이 문제에서는 E=O(V)이므로 총 시간복잡도는 O(V)

===== 코드 =====
(다이아몬드 이상은 코드 생략)
  * Dependency 
    * [[:ps:teflib:graph#create_graph_from_input|teflib.graph.create_graph_from_input]]
    * [[:ps:teflib:graph#two_coloring|teflib.graph.two_coloring]]

{{tag>BOJ ps:problems:boj:다이아몬드_3}}