티스토리 뷰

[Code jam] C번 문제 (2016 Round1 A)

문제 요약

어린이집에 N명의 어린이들이 있다. 이 어린이집에서는 원으로 둘러 앉아서 하는 활동을 한다. 이때 어린이 왼쪽 또는 오른쪽에 자기가 생각하는 베스트 프랜드가 앉아있어야한다.

베스트 프렌드는 반드시 한명이다. 불행히도 철수는 영희가 자신의 베스트 프랜드라고 생각하더라도 영희는 철수를 베스트 프랜드라고 생각하지 않을 수 있다.

각 어린이들의 자신의 베스트 프랜드가 주어질 때 최대 몇 명이 둘러 앉아서 활동을 할 수 있는지를 구해야한다. 이때 각 어린이들은 1~N사이의 서로다른 학생 번호를 가진다.

입력 예시

4
2 3 4 1

어린이 4명이 있다. 각 어린이의 베스트 프랜드는 아래 표와 같음을 알 수 있다.

어린이 번호 자신의 베스트 프랜드 어린이 번호
1 2
2 3
3 4
4 1

이때 그림1과 같이 앉으면 모든 어린이의 왼쪽 또는 오른쪽에 자신의 베스트 프랜드가 있기 때문에 이 입력에 대해 최대 4명의 어린이가 원형으로 둘러앉아 활동을 할 수 있다.

그림1그림1

생각 흐름

각 어린이를 정점으로 나타내고 어린이의 베스트 프랜드를 방향그래프로 표현한다. 위 입력 예시는 그림2와 같은 방향그래프로 나타낼 수 있다.

그림2그림2

그러면 직관적으로 구성된 방향그래프에서 나타나는 사이클의 최대 길이를 출력하면 답을 구할 수 있다는 생각이 든다.

그러나 4번째 입력 예시를 직접 그려보면 그림3과 같은 방향그래프로 나타낼 수 있는데

4번째 입력 예시
10
7 8 10 10 9 2 9 6 3 3

그림3그림3

이 그래프에서 3, 10번 정점으로 구성된 길이2 사이클 밖에 없지만 최대 6명(7 9 3 10 4 1번어린이)가 원형으로 같이 앉을 수 있다고 문제에 힌트가 주어진다. 이 힌트가 없었다면 훨씬 더 많은 사람들이 틀렸을거 같다.

그림3의 그래프에서 최대 6명의 어린이가 원형으로 앉은것을 나타내면 그림4와 같이 나타낼 수 있다.

그림4그림4

그러면 길이가 2인 사이클의 한쪽 정점을 가리키는 빨간색 간선과 다른 한쪽 정점으로 연결되는 파란색 간선들로 구성되어 있음을 알 수 있다. 따라서 길이 2사이클에 위와 같이 연결된 형태도 답의 후보로 고려해야한다.

이제 솔루션에 거의 근접한거 같다. 혹시 놓친게 없을까? 만약 길이 2사이클에 연결된 집합이 여러 개이면 답은 어떻게 될까?

그 집합안에 있는 어린이들은 반드시 자신의 베스트 프랜드가 옆에 앉아 있기 때문에 이를 이어 붙여서 원형으로 앉아도 모든 어린이들의 옆에 자신의 베스트 프랜드가 옆에 앉아 있을 것이다.

솔루션

  1. 어린이의 베스트 프랜드 관계를 그래프로 구성한다.
  2. 그래프에서 최대 길이 사이클을 구한다.
  3. 길이가 2인 사이클에 연결된 집합을 모두 구하고 길이를 합한다.
  4. 2번과 3번에서 구한 값 중에 큰 것을 답으로 한다.

코드

솔루션 1, 2번 과정은 매우 간단해서 설명을 생략한다.
솔루션 3번 과정은 길이가 2인 사이클을 찾으면 사이클을 구성하는 양쪽 정점에서 역방향으로 BFS를 돌려서 최대값을 더하면 된다. 그러나 아래 코드에서는 이 과정을 2줄로 구현하기 위해 벨만포드 알고리즘의 아이디어를 이용해서 indegree가 0인 노드에서 이 길이가 2인 사이클의 두 정점까지의 거리를 구하는 방식을 사용했다.


댓글
최근에 달린 댓글
Total
Today
Yesterday