algospot 회의실 배정(문제 ID: MEETINGROOM) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MEETINGROOM

algospot.com :: MEETINGROOM

각 팀마다 두개의 회의가 있고 각 회의마다 시작시간과 종료시간이 입력으로 주어진다.

각 팀들이 다른 팀들과 시간이 안겹치게 회의를 딱 하나씩만 할 수 있는지, 할 수 있다면 각 팀의 회의 시간을 출력하는 문제이다.

 

 

해당 문제는 SCC(강 결합 컴포넌트)를 이용한 2-SAT문제로 해결 할 수 있다.

먼저 각 회의마다 참인 경우와 거짓인 경우 각각 두 개의 정점으로 표현하여 각 팀에 두 회의 관계를 그래프로 나타낸다.

팀은 두 회의 중 반드시 하나의 회의만 해야한다. 이를 표현식으로 나타내면 다음과 같다.

~i => j 앞에 회의를 안했다면 뒤에 회의를 꼭 해야한다.

~j => i 뒤에 회의를 안했다면 앞에 회의를 꼭 해야한다.

i => ~j 앞에 회의를 했다면 뒤에 회의는 꼭 하지 말아야 한다.

j => ~i 뒤에 회의를 했다면 앞에 회의는 꼭 하지 말아야 한다.

 

그리고 각 회의마다 겹치는 시간에 대한 관계 또한 그래프로 나타낸다.

두 회의가 시간이 겹칠 경우 최대 한개의 회의만 할 수 있다. 이를 표현식으로 나타내면 다음과 같다.

i => ~j 시간이 겹치는 두 회의 중 한개를 했다면 다른 한개는 하지 말아야 한다.

j => ~i 시간이 겹치는 두 회의 중 한개를 했다면 다른 한개는 하지 말아야 한다.

 

이러한 관계를 적절히 그래프로 표현한 다음 SCC를 이용하여 참 컴포넌트와 거짓 컴포넌트를 구분한 후 위상정렬하여,

첫 컴포넌트를 거짓이라 가정하고 차례로 컴포넌트에 속한 정점들의 참 거짓값을 채워 나가면 된다.

 

코드 원본 : https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/MEETINGROOM.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2