[백준 14588] Line Friends (Small) (Java)

문제 링크: https://www.acmicpc.net/problem/14588

14588번: Line Friends (Small)

1. 주의할 점

- 2개의 선분이 겹치는 조건을 잘 생각한다

- 플로이드 와샬 알고리즘에 대하여 알고 있어야한다

- 양방향 그래프이므로 플로이드 와샬을 사용할 경우, 배열의 원소를 잘 초기화 해야한다(내 코드의 경우 한번에 2개의 원소를 초기화 해야 한다)

 

2. 구현

- Arr[][]배열을 전부 987654321로 초기화하며, i==j인 경우에만 0으로 초기화한다

- 각 선분에 대한 정보를 입력받은 후, 2개의 선분(I,J)을 비교하여 겹치는 부분이 있다면 Arr[I][J], Arr[J][I]값을 1로 바꾼다

- 플로이드 와샬 알고리즘을 사용하며 Arr[][] 배열을 최적화한다

- 질의에 맞는 답을 출력한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int arr[][];
	static int l[], r[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine().trim());

		// 초기화
		arr = new int[n + 1][n + 1];
		l = new int[n + 1];
		r = new int[n + 1];
		for (int i = 1; i < n; i++)
			for (int j = i; j <= n; j++) {
				if (i == j)
					arr[i][j] = 0;
				else {
					arr[i][j] = 987654321;
					arr[j][i] = 987654321;
				}
			}

		for (int i = 1; i <= n; i++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			l[i] = Integer.parseInt(st.nextToken());
			r[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i < n; i++)
			for (int j = i + 1; j <= n; j++)
				if ((l[i] <= l[j] && l[j] <= r[i]) || (l[i] <= r[j] && r[j] <= r[i])
						||(l[j] <= l[i] && l[i] <= r[j]) || (l[j] <= r[i] && r[i] <= r[j])) {
					arr[i][j] = 1;
					arr[j][i] = 1;
				}

		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					if (arr[i][j] > arr[i][k] + arr[k][j])
						arr[i][j] = arr[i][k] + arr[k][j];

		int query = Integer.parseInt(br.readLine().trim());
		for (int i = 0; i < query; i++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			System.out.println(arr[a][b] == 987654321 ? -1 : arr[a][b]);
		}
	}
}