[BOJ] 14588 Line Friends (Small)

문제 개요

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

아이디어

각 선에 대해서 친구 관계인지 먼저 확인하고, 친구 관계라면 graph값 = 1로 세팅한다.
그리고 플로이드-와샬 알고리즘 돌려서 친구 관계를 확인한다.
초기값인 0이라면 친구 관계가 단절되어있다는 뜻.

18243번: Small World Network

이 문제에 냈던 코드를 거의 그대로 썼다 ㅎㅎ;

코드

typedef long long ll;
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<math.h>
#include<stack>
using namespace std;

int N, Q;
struct edge {
	int L, R;
};
edge info[305];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int L, R; cin >> L >> R;
		info[i].L = L; info[i].R = R;
	}

	int graph[305][305] = { 0, };
	// 먼저 2중for문 돌면서 각자 친구 관계인지 확인한다
	// 친구라면 graph=1;
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			// info[i]와 info[j] 관계로 파악
			bool fri = false;
			if (info[j].L <= info[i].R && info[i].L <= info[j].R) fri = true;
			if (info[i].L < info[j].R && info[j].L <= info[i].R) fri = true;
			if (fri) {
				graph[i][j] = 1;
				graph[j][i] = 1;
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				if (j == k) continue;
				if (graph[j][i] != 0 && graph[i][k] != 0) {
					if (graph[j][k] > graph[j][i] + graph[i][k]) {
						graph[j][k] = graph[j][i] + graph[i][k];
					}
					else if (graph[j][k] == 0) {
						graph[j][k] = graph[j][i] + graph[i][k];
					}
					else;
				}
			}
		}
	}

	cin >> Q;
	while (Q--) {
		int a, b; cin >> a >> b;
		if (graph[a][b] == 0) cout << "-1\n";
		else cout << graph[a][b] << "\n";
	}

	return 0;
}

다른 블로그를 찾아봤는데 (출처: https://donggod.tistory.com/74)

if (v[a].second < v[b].first || v[b].second < v[a].first) return 0;

이걸로 겹침을 판단할 수 있었다. 즉, a의 R < b의 L이거나 b의 R < a의 L 이라면 안 겹치고 그 외의 경우는 모두 겹친다는 것.

겹치는거 판단하는 코드가 조금 어려웠는데 이렇게 하면 좀더 깔끔했을거같다.