취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1739번 문제인 도로 정비하기이다.
문제는 아래 링크를 확인하자.

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

각 도로의 방향은 가로방향 도로는 왼쪽 또는 오른쪽, 세로방향 도로는 위쪽 또는 아래쪽 둘 중 하나이고, 두 상태 모두가 동시에 만족될 수는 없으므로 이를 TF와 같이 생각하여 모든 명제들을 만족시키는 상황을 찾는 문제로 변형할 수 있다.

각 도로의 방향별로 노드를 하나씩 만들고 아래와 같은 규칙으로 조건식을 세워 에지로 채워넣자:

주어지는 버스노선의 출발지와 도착지가 같다면 처리를 하지 않는다.

출발지와 도착지가 같은 도로 위에 있다면 그 도로의 방향을 정해준다.

그렇지 않다면, 가능한 두 경로중 한 경로가 이용이 불가능한(즉, 어떤 하나의 도로가 방향이 반대인) 경우에 다른 경로 둘이 적절한 방향으로 있어야한다는 식을 세운다.

만약 한 도로가 이 방향이기도 해야하고 반대방향이기도 해야하는, 모순적인 상황이 발생한다면(같은 SCC 안에 들어있을 경우) 문제에서 구하는 도로망은 존재하지 않는다. 그렇지 않다면 그러한 도로망은 항상 존재한다.

아래의 구현에서, 노드의 인덱스는 (가로방향 도로들) (세로방향 도로들) (가로방향 도로들 역방향) (세로방향 도로들 역방향) 순이다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N, M, total, K;
vector<int> G[4001];
int dfi[4001], dfidx;
int sci[4001], scidx;
vector<int> stk;
int dfs(int current) {
	stk.emplace_back(current);
	int ret = dfi[current] = dfidx++;
	for (auto node : G[current]) {
		if (sci[node]) continue;
		if (dfi[node]) ret = min(ret, dfi[node]);
		else ret = min(ret, dfs(node));
	}

	if (ret == dfi[current]) {
		while (stk.back() != current) {
			sci[stk.back()] = scidx;
			stk.pop_back();
		}
		sci[current] = scidx++;
		stk.pop_back();
	}

	return ret;
}

void solve() {
	cin >> N >> M >> K;
	total = N + M;
	int total2 = total * 2 + 1;
	for (int i = 1; i < total2; i++) G[i].clear();
	memset(dfi, 0, sizeof(dfi));
	memset(sci, 0, sizeof(sci));
	dfidx = scidx = 1;

	while (K--) {
		int A, B, C, D; cin >> A >> B >> C >> D;
		B += N, D += N;
		if (A == C && B == D) continue;
		if (A == C) {
			if (B < D) G[A + total].emplace_back(A);
			else G[A].emplace_back(A + total);
		}
		else if (B == D) {
			if (A < C) G[B + total].emplace_back(B);
			else G[B].emplace_back(B + total);
		}
		else {
			if (A < C && B < D) {
				G[B + total].emplace_back(A);
				G[B + total].emplace_back(D);
				G[C + total].emplace_back(A);
				G[C + total].emplace_back(D);
				G[A + total].emplace_back(B);
				G[A + total].emplace_back(C);
				G[D + total].emplace_back(B);
				G[D + total].emplace_back(C);
			}
			else if (A < C && B > D) {
				G[A].emplace_back(B);
				G[A].emplace_back(C + total);
				G[D + total].emplace_back(B);
				G[D + total].emplace_back(C + total);
				G[B + total].emplace_back(A + total);
				G[B + total].emplace_back(D);
				G[C].emplace_back(A + total);
				G[C].emplace_back(D);
			}
			else if (A > C && B < D) {
				G[B].emplace_back(A);
				G[B].emplace_back(D + total);
				G[C + total].emplace_back(A);
				G[C + total].emplace_back(D + total);
				G[A + total].emplace_back(B + total);
				G[A + total].emplace_back(C);
				G[D].emplace_back(B + total);
				G[D].emplace_back(C);
			}
			else {
				G[A].emplace_back(B + total);
				G[A].emplace_back(C + total);
				G[D].emplace_back(B + total);
				G[D].emplace_back(C + total);
				G[B].emplace_back(A + total);
				G[B].emplace_back(D + total);
				G[C].emplace_back(A + total);
				G[C].emplace_back(D + total);
			}
		}
	}

	for (int i = 1; i < total2; i++) {
		if (sci[i]) continue;
		dfs(i);
	}

	bool chk = 1;
	for (int i = 1; i <= total; i++) {
		if (sci[i] == sci[i + total]) chk = 0;
	}

	if (chk) cout << "Yes\n";
	else cout << "No\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		solve();
	}
}