[BOJ 3648] 아이돌

백준 3648번 아이돌

https://www.acmicpc.net/problem/3648

3648번: 아이돌

---

문제

한 심사위원이 두 표를 행사합니다.

행사한 두 표 중에 적어도 하나는 결과가 만족해야합니다.

 

추가로 상근이는 반드시 합격 목록에 들어가 있어야 합니다.

---

풀이

4 3
1 2
-2 -3
2 4

예제 입력이 위와 같이 주어집니다.

총 3명의 심사위원이 두명한테 투표를 행사했습니다.

 

양수는 해당 number가 합격해야 한다는 의미이고,

음수는 해당 number가 불합격해야 한다는 의미입니다.

 

1) 1 2

1번이 불합격하면, 2번은 합격해야 합니다.

2번이 불합격하면, 1번은 합격해야 합니다.

 

2) -2 -3

2번이 합격하면, 3번은 불합격해야 합니다.

3번이 합격하면, 2번은 불합격해야 합니다.

 

3) 2 4

2번이 불합격하면, 4번은 합격해야 합니다.

4번이 불합격하면, 2번은 합격해야 합니다.

---

이는 2-sat으로 문제를 풀 수 있습니다.

https://kdr06006.tistory.com/8

2-SAT

 

그래프 모델링

2-sat을 이용해 그래프 모델링을 한 모습입니다.

---

추가로 상근이는 합격을 해야만 합니다.

즉, 1번은 true 값을 가져야 한다는 소리입니다.

 

그래프 모델링을 통해 관계식을 추출할 수 있습니다.

p -> q의 간선이 있을 때, p의 값을 false로 설정해주면 됩니다.

 

p의 값을 false로 만들고 싶다면 p -> q 간선을 추가해주면 됩니다.

not 1 값을 false로 만들고 싶기에, not 1 -> 1 간선을 추가해 줍니다.

---

코드

#include <cstdio>

const int VSIZE = 2e3 + 4;
const int ESIZE = 4e3 + 4;

struct EdgePool {
	EdgePool* next;
	int x;
}edgePool[ESIZE];

int N, edgeCnt;

EdgePool* getEdge(int x) {
	edgePool[edgeCnt].x = x;
	edgePool[edgeCnt].next = NULL;
	return &edgePool[edgeCnt++];
}

struct Vector {
	EdgePool* head;

	void push(int x) {
		EdgePool* cur = getEdge(x);
		cur->next = head;
		head = cur;
	}
}adj[VSIZE];

struct Stack {
	int arr[VSIZE];
	int top = -1;

	inline bool empty() { return top == -1; }
	inline void push(int n) { arr[++top] = n; }
	inline int pop() { return arr[top--]; }
};

inline int get(int x) { return x > 0 ? x : -x + N; }
inline int min(int a, int b) { return a < b ? a : b; }

struct SCC {
	int dfsn[VSIZE], dfsNumber;
	int sccn[VSIZE], sccNumber;
	bool finish[VSIZE];
	Stack S;

	void init() {
		dfsNumber = sccNumber = 0;
		for (register int i = 1; i <= 2 * N; ++i) 
			finish[i] = dfsn[i] = 0;
	}

	void solve() {
		for (register int i = 1; i <= 2 * N; ++i) {
			if (!dfsn[i]) dfs(i);
		}

		printf("%s\n", TOF() ? "yes" : "no");
	}

	int dfs(int cur) {
		int ret = dfsn[cur] = ++dfsNumber;
		S.push(cur);

		for (EdgePool* e = adj[cur].head; e; e = e->next) {
			int n = e->x;
			if (!dfsn[n]) ret = min(ret, dfs(n));
			else if (!finish[n]) ret = min(ret, dfsn[n]);
		}

		if (ret == dfsn[cur]) {
			++sccNumber;

			while (!S.empty()) {
				int t = S.pop();
				sccn[t] = sccNumber;
				finish[t] = true;
				if (t == cur) break;
			}
		}

		return ret;
	}

	bool TOF() {
		for (register int i = 1; i <= N; ++i) {
			if (sccn[i] == sccn[i + N]) return false;
		}

		return true;
	}
}scc;

void init() {
	for (register int i = 1; i <= 2 * N; ++i)
		adj[i].head = NULL;
	edgeCnt = 0;
	scc.init();
}

int main()
{
	//freopen("input.txt", "r", stdin);

	int m;
	while (scanf("%d %d", &N, &m) == 2) {
		init();

		int x, y;
		while (m--) {
			scanf("%d %d", &x, &y);
			adj[get(-x)].push(get(y));
			adj[get(-y)].push(get(x));
		}

		adj[1 + N].push(1);

		scc.solve();
	}
}

---

감사합니다.