BOJ 2516 (원숭이) - CT 풀이

 만나면 좋은 친구도 많지만, 우리는 살다 보면 그 반대의 사람도 상당히 많이 만나게 됩니다. 보통의 경우에는 그런 사람과 최대한 만날 상황을 피하려고 하게 되지만 직장 생활을 하게 되면 그럴 수 없는 경우가 더 많이 있습니다. 문제의 원숭이들도 앙숙 원숭이와 만나는 상황을 피하고 싶어 하지만 2개의 우리밖에 없는 상황에서 모든 앙숙과 피하는 것은 어려운 일이죠. 그래서 원숭이마저도 1명의 앙숙 하고 같이 지내는 것은 이해하는 모습을 보입니다. ㅎㅎ

 

 우리 역시도 앞서 말한 것처럼 언제나 앙숙들을 만납니다. 회사에 들어가서 역시 마찬가지일테고요. 하지만 회사 생활이 군대도 아니고, 언제 끝날지 모르는 상황에서 욕만 하고 사는 것도 쉽지 않습니다. 또, 그 사람 때문에 회사의 모든 것이 다 싫어진다면 더 큰 스트레스가 될 것이 분명하죠. 그러지 않으려면, 우리는 인정하는 법을 배워야 합니다. 사람은 밉지만, 그래도 그 사람 덕분에 좋았던 것에 대해서는 인정할 수 있고, 칭찬할 수 있어야 그 사람도 나에 대해 조금이라도 더 우호적으로 대할 수 있으니까요. 마치 문제의 원숭이들처럼 우리도 어느 정도 앙숙을 이해하고 타협할 수 있다면 분명 많은 단체 생활 속에서 조금 더 잘 살아갈 수 있을 것이라고 생각합니다!!

 

(물론 1명보다 많은 앙숙들이 날 둘러싸고 있다면... 좀 더 힘들 수는 있겠네요. ㅠ) 

---

 

2516번: 원숭이

문제 설명)

 원숭이를 넣을 우리는 총 두개가 있고, 원숭이는 N마리 있습니다. 그리고, 각 원숭이는 최대 3마리까지 앙숙을 가지고 있습니다. 두 우리에 원숭이들을 넣는 조건이 다음과 같을 때에 규칙에 맞도록 각 우리에 원숭이들을 배치하는 경우를 출력하는 문제입니다.

 

우리에 원숭이를 넣는 조건

1. 각 원숭이에 대해 같은 우리 안에 있으며 앙숙 관계인 원숭이는 한 마리 이하이다.
2. 비어있는 우리는 없다. (즉, 하나의 우리에 원숭이를 모두 수용 가능한 경우가 있더라도 각각의 우리에는 적어도 한 마리 이상의 원숭이를 수용하여야 한다.)

 

예제 입력

# N(원숭이의 수)
5
# M(각 원숭이의 앙숙관계에 있는 원숭이 수), M마리의 원숭이 번호 : 1 ~ N줄
3 2 3 4
3 1 3 5
3 1 2 4
3 1 3 5
2 2 4

---

문제 풀이)

  이 문제는 처음 보면서 1, 2번의 과정이 없으니 DP도 아니고, 트리나 그래프도 아니고, 그리디로 풀리지도 않길래 도대체 무슨 알고리즘인 것인가 의문이 들었습니다. 그러다 단순히 그림을 그려서 우리에 하나씩 넣어보았는데 어느 정도 문제가 풀리는 게 보였습니다. 후에 알고 보니 '어떻게 푸는지는 알겠는데, 어떤 알고리즘으로 어떻게 코드로 구현할지 모르겠는 문제들'이 보통 '구현' 알고리즘 문제라고 한다는 것을 알았죠.

 

 이 문제 역시 '구현 알고리즘' 문제로, 대충 머리속으로 풀리는 것이 어떠한 방식으로 해결되는 것인지 파악하고, 이를 1, 2, 3의 과정으로 정리해서 다음 문제에도 적용하면 되겠습니다. 

 

 자, 이제 예제 입력 1을 보고 문제를 풀어보겠습니다.

 

참고 1 ) 원숭이 앙숙 관계 그래프

 

 그래프에서 각 노드는 원숭이들을 의미하고, 간선으로 연결된 원숭이끼리는 앙숙 관계임을 의미합니다. 이 그래프를 참고해서 원숭이들을 1번부터 인덱스 순서대로 1, 2번 우리에 넣을 때에 어떻게 하면 앙숙 관계인 원숭이들을 최대한 피해서 넣을 수 있을까요? 일단, 한 마리씩 넣어보도록 하겠습니다.

우리	1	2
원숭이	1

 

 1번 원숭이를 일단 우리 1에 넣었습니다. 그럼 2번 원숭이를 넣어야 하는데, 어디다 넣는 편이 좋을까요? 

 간단하게 생각해서 앙숙 관계인 원숭이가 적은 곳으로 넣으면 됩니다. 간단하죠. 그럼 2번 원숭이를 2번 우리에 넣겠습니다.

우리	1	2
원숭이	1	2

 

 자 다음은 3번 원숭이 입니다. 3번 역시 더 앙숙 관계인 원숭이가 적은 곳으로 넣으려고 하니까.. 이럴 수가! 두 우리 모두 한 마리씩 동률입니다. 그렇다면 일단 3번 원숭이는 제쳐두고 4번 원숭이부터 넣도록 하겠습니다. 

 4번 원숭이는 1번 우리에 1마리의 앙숙, 2번 우리에 0마리의 앙숙이 있습니다. 그렇기 때문에 2번 우리에 넣습니다.

우리	1	2
원숭이	1	2, 4

 

 다음으로 5번 원숭이를 넣어봅시다. 5번 원숭이는 1번 우리에 0마리의 앙숙, 2번 우리에 2마리의 앙숙이 있으므로 1번 조건에 따라 무조건 1번 우리로 넣어야 합니다.

우리	1	2
원숭이	1, 5	2, 4

 

 이제 마지막으로 3번 원숭이로 다시 돌아가서 생각해봅시다. 이번에도 동률일까요? 

 이번에는 1번 우리에 앙숙 1마리, 2번 우리에 앙숙 2마리로 다른 결과가 나왔습니다. 즉, 3번 원숭이를 1번 우리에 넣으면 우리는 위의 조건에 맞추어 원숭이들을 두 우리로 모두 나눌 수 있게 되겠습니다.

우리	1	2
원숭이	1, 3, 5	2, 4

 

 이렇게 답을 도출하기까지 우리가 쓴 방법은 무엇일까요? 바로 다음과 같이 정리할 수 있습니다.

 

1. 인덱스 순서대로 원숭이를 앙숙이 더 적은 우리에 넣는다. (1번 원숭이의 경우 아무 우리나 넣는다.)
2. 앙숙의 수가 두 우리 모두 같다면 해당 원숭이를 맨 마지막으로 미룬다.
   • 만약 미룬 원숭이 순번으로 돌아왔음에도 2번의 경우가 반복된다면, 아무 우리에나 넣는다.
3. 원숭이를 모두 우리에 넣을 때까지 반복

 

 그리고, 이 과정대로 다음 예제도 풀어보면서 이 과정이 옳은지 확인하면 됩니다. 

 

---

​

예제 입력 2

6
1 2
1 1
0
1 5
2 4 6
1 5

 

 1번 원숭이를 1번 우리에 넣는다.

우리	1	2
원숭이	1

 

 2번 원숭이를 2번 우리에 넣는다. (앙숙 1마리 vs 0마리)

우리	1	2
원숭이	1	2

 

 3번 원숭이는 0마리 vs 0마리 동률이므로 넘어간다. 

 4번 원숭이는 0마리 vs 0마리 동률이므로 넘어간다.

 5번 원숭이는 0마리 vs 0마리 동률이므로 넘어간다.

 6번 원숭이는 0마리 vs 0마리 동률이므로 넘어간다.

 

 3번 원숭이를 1번 우리에 넣는다. (다시 비교해도 똑같이 동률이므로..)

우리	1	2
원숭이	1, 3	2

 

 4번 원숭이를 1번 우리에 넣는다. (다시 비교해도 똑같이 동률이므로..)

우리	1	2
원숭이	1, 3, 4	2

 

 5번 원숭이를 2번 우리에 넣는다. (앙숙 1마리 vs 0마리)

우리	1	2
원숭이	1, 3, 4	2, 5

 

 마지막으로 6번 원숭이를 1번 우리에 넣는다. (앙숙 0마리 vs 1마리)

우리	1	2
원숭이	1, 3, 4, 6	2, 5

 

 예제 출력 2와 다르지만, 실제로 앙숙 관계를 따져보면 해당 경우도 가능한 것을 확인할 수 있습니다.