티스토리 뷰

IOI/IOI2012

[IOI2012 Day1] Rings 해법

전명우 2013. 7. 22. 10:25

문제 ↓

rings.pdf

문제의 고리를 노드로 고리끼리 연결이 되면 간선으로 연결을 해주어 그래프로 표현할 수 있다.
문제의 해법에 접근하기 위해서는 다음과 같은 사실들을 관찰할 필요가 있다.

  • 만약 차수가 4 이상인 노드가 존재하면, 다른 노드들은 중요한 고리가 될 수 없다. 다른 노드를 제거하면 차수가 3이상인 노드가 남기 때문이다. 같은 의미로 차수가 4이상인 노드가 여러 개면 중요한 고리는 존재하지 않는다.
  • 만약 차수가 3인 노드 $V$가 존재하면, 모든 중요한 고리는 $V$ 혹은 $V$에 연결된 노드들 중에 있다.
  • 만약 싸이클이 존재하면, 모든 중요한 고리는 싸이클 안에 있다.
  • 만약 그래프가 여러 개의 직선으로 구성되어 있으면, 모든 고리가 중요한 고리다.

위 사실들을 이용하여 중요한 고리의 개수를 O(1) 만에 구할 수 있다. 차수가 3인 노드가 존재할 때와 존재하지 않을 때 나누어서 코딩하면 편하다. 차수가 3인 노드가 존재할 때에는 중요한 고리가 될 수 있는 후보 4개에 대해 각각 그 노드가 없을 때에 대해 코딩을 해주면 된다.

'IOI > IOI2012' 카테고리의 다른 글

[IOI2012 Day2] City 해법  (0) 2013.07.23
[IOI2012 Day2] Super 해법  (0) 2013.07.23
[IOI2012 Day2] Tournament 해법  (0) 2013.07.22
[IOI2012 Day1] Scrivener 해법  (0) 2013.07.22
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함