티스토리 뷰

IOI/IOI2012

[IOI2012 Day1] Rings 해법

전명우 2013.07.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] Rings 해법  (2) 2013.07.22
[IOI2012 Day1] Scrivener 해법  (0) 2013.07.22
댓글
  • 프로필사진 질문있습니다. 좋은 글 써주셔서 감사합니다. 근데 cycle 개수를 어떻게 세는지 잘 모르겠습니다. cycle_cnt로 세는 것 같은데 정확하게 어떻게 세는지 알려주시면 감사하겠습니다. 2015.01.02 14:06 신고
  • 프로필사진 전명우 풀이 작성한지 오래되어 확실하지 않지만, 코드를 보니 union find (+ path compression)으로 cycle인지 확인하며 개수를 세었네요. 2015.03.16 11:17 신고
댓글쓰기 폼