[알고리즘] 백준 14588번: Line Friends (Small)

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

14588번: Line Friends (Small)

1) 선분 간의 관계가 친구임을 입증할만한 함수가 필요하다.

2) 선분(노드)끼리 친구라면 서로 관계에 대한 가중치를 1로 둔다.

3) 플로이드 와샬을 돌린다.

---

1) 선분 간의 관계가 친구임을 입증할만한 함수가 필요하다. >> 이 부분이 제일 까다로웠다.

2) 선분(노드)끼리 친구라면 서로 관계에 대한 가중치를 1로 둔다.

 

선분 구조체를 선언하여 한 노드의 왼쪽 점과 오른쪽 점을 담아주었다.

typedef struct {
	int left, right;
}line;

둘 사이의 친구관계를 입증하기 위해 다음과 같은 함수를 만들었다.

void floydInit() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (node[i].right < node[j].left || node[j].right < node[i].left) {
				continue;
			}
			graph[i][j] = 1;
			graph[j][i] = 1;
		}
	}
}

안 되는 사례들을 continue시키는 게 덜 복잡하다. 되는 사례들을 조건으로 잡으려다가 반대로 생각해보자는 방법이 떠올랐었다.

[AC 코드]

#include <iostream>
#include <vector>
#define MAX 300 + 1
#define INF 987654321
using namespace std;

typedef struct {
	int left, right;
}line;

line node[MAX];
int graph[MAX][MAX];
int n;

void floydInit() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (node[i].right < node[j].left || node[j].right < node[i].left) {
				continue;
			}
			graph[i][j] = 1;
			graph[j][i] = 1;
		}
	}
}

void floydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][k] == INF && graph[k][j] == INF) continue;
				if (graph[i][j] > graph[i][k] + graph[k][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
				}
			}
		}
	}
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

	for (int i = 1; i <= n; i++) {
		cin >> node[i].left >> node[i].right;
	}

	floydInit();
	floydWarshall();
	
	int q;
	cin >> q;
	for (int i = 0, a, b; i < q; i++) {
		cin >> a >> b;
		if (graph[a][b] == INF) cout << -1 << '\n';
		else cout << graph[a][b] << '\n';
	}

	return 0;
}