반응형
🔺 문제
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
import java.util.*;
import java.io.*;
public class Main {
static int[] parent = new int[3001]; // 부모 노드 저장 배열
static int[][] L = new int[3001][4]; // 선분 저장 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine()); // 선분 갯수
for(int i = 1 ; i <= N ; i++) {
parent[i] = -1;
}
// 신규 선분 저장
for(int i = 1 ; i <= N ; i++) {
st = new StringTokenizer(br.readLine()," ");
L[i][0] = Integer.parseInt(st.nextToken());
L[i][1] = Integer.parseInt(st.nextToken());
L[i][2] = Integer.parseInt(st.nextToken());
L[i][3] = Integer.parseInt(st.nextToken());
// 이전에 저장된 선분들과 교차 여부 확인
for(int j = 1 ; j < i ; j++) {
if(isCross(L[i][0], L[i][1], L[i][2], L[i][3], L[j][0], L[j][1], L[j][2], L[j][3])) {
union(i, j);
}
}
}
int ans = 0; // 선분 그룹 수
int res = 0; // 가장 큰 선분 그룹의 선분 수를 음수로 저장하는 변수
for(int i = 1 ; i <= N ; i++) {
if(parent[i] < 0) { // 음수면, 선분 그룹을 대표 부모 노드
ans++; // 선분 그룹 수 증가
res = Math.min(res, parent[i]); // 음수의 절댓값이 선분 그룹의 선분 개수
}
}
System.out.println(ans);
System.out.println(-res);
}
// 유니온파인드
static int find(int i) {
if(parent[i] < 0) return i;
return parent[i] = find(parent[i]);
}
static void union(int a, int b) {
int p = find(a);
int q = find(b);
if(p == q) return; // 이미 연결됨
parent[p] += parent[q]; // p의 부모 노드에 q가 속한 선분 그룹의 선분 개수 더하기
parent[q] = p; // p를 q의 부모 노드로 저장
}
// CCW
private static int CCW(long x1, long y1, long x2, long y2, long x3, long y3) {
long tmp = (x1*y2 + x2*y3 + x3 * y1) - (x2*y1 + x3*y2 + x1*y3);
if(tmp > 0) return 1; // 반시계
else if(tmp < 0) return -1; // 시계
return 0; // 일직선
}
// 선분 겹치는지 판단
private static boolean isOverlap(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4) {
if(Math.min(x1, x2) <= Math.max(x3, x4) && Math.min(x3, x4) <= Math.max(x1, x2)
&& Math.min(y1, y2) <= Math.max(y3, y4) && Math.min(y3, y4) <= Math.max(y1, y2))
return true;
return false;
}
// 교차 여부 판단
private static boolean isCross(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4) {
int abc = CCW(x1, y1, x2, y2, x3, y3);
int abd = CCW(x1, y1, x2, y2, x4, y4);
int cda = CCW(x3, y3, x4, y4, x1, y1);
int cdb = CCW(x3, y3, x4, y4, x2, y2);
// 선분이 일직선일 때
if(abc * abd == 0 && cda * cdb == 0) {
return isOverlap(x1, y1, x2, y2, x3, y3, x4, y4);
}
// 선분이 교차하는 경우
else if(abc * abd <= 0 && cda * cdb <= 0) {
return true;
}
return false;
}
}
|
cs |
✅ 해결 아이디어
✔ 분리 집합 & 선분 교차 판정
🔺 다른 풀이들
- 멋진 해설...
💬 느낀 점
유니온 파인드 오랜만입니다ㅎㅎ
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 3460번: 이진수 (0) | 2023.05.19 |
---|---|
[백준/JAVA] 2166번: 다각형의 면적 (1) | 2023.05.18 |
[백준/JAVA] 17387번: 선분 교차 2 (0) | 2023.05.18 |
[백준/JAVA] 11758번: CCW (0) | 2023.05.18 |
[백준/JAVA] 2098번: 외판원 순회 (0) | 2023.05.17 |