PS/BOJ
3108
easy16
2022. 5. 2. 00:27
로고 : https://www.acmicpc.net/problem/3108
실패 : 사각형 포함여부를 결정하는 조건(isConnected) 에 대해서 다시 살펴 볼것.
고찰 :
1. 시작지점 (0,0)을 Rect(0,0,0,0)으로 표현 할 수 있다.
2. BFS를 반복문으로 호출하고, 반복하는 횟수를 counting하는 방식으로 PU 개수를 결정.
예제의 조건으로 살펴보면,
5
1 1 4 4
3 3 6 6
4 4 5 5
5 0 8 3
6 1 7 2i=0
B(0) -> X : 시작점과 연결된 경로 없음 cnt = 1. visited 0,
i=1
B(1) -> B(2) -> B(3) -> B(4) cnt=2; visited 0,1,2,3,4
i=2,3,4 continue
i=5,
B(5) cnt=3 , visited 0,1,2,3,4,5
cnt는 3개지만 문제 조건상 PD 상태로 시작되므로 실제 PU 동작은 2회(cnt-1) 필요하다.
isConnected 의 판단 조건 (시점이 종점보다 작다는 가정하에 성립 : 입력조건에서 확인가능)
한붓그리기가 불가능한 경우는 아래와 같다.
1. current가 next안에 포함됨 or next가 current안에 포함됨.
2. next의 종점보다 current의 시점이 크다. or current의 종점이 next의 시점보다 작다.
즉, 두 Rect가 서로 떨어져 있거나, 선이 겹치지 않도록 포함되는 경우를 제외하면 Connected로 판단한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static boolean DBG = false;
static int N, M, K;
static Rect[] arr;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new Rect[N + 1];
visited = new boolean[N + 1];
// 원점을 다음과 같이 직사각형으로 표현
arr[0] = new Rect(0, 0, 0, 0);
for (int i = 1; i <= N; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine());
int sx = Integer.parseInt(st.nextToken());
int sy = Integer.parseInt(st.nextToken());
int ex = Integer.parseInt(st.nextToken());
int ey = Integer.parseInt(st.nextToken());
arr[i] = new Rect(sx, sy, ex, ey);
}
/*
* System.out.println("0 vs 1 : " + isConnected(arr[0], arr[1]));
* System.out.println("1 vs 2 : " + isConnected(arr[1], arr[2]));
* System.out.println("2 vs 3 : " + isConnected(arr[2], arr[3]));
* System.out.println("3 vs 4 : " + isConnected(arr[3], arr[4]));
* System.out.println("4 vs 5 : " + isConnected(arr[4], arr[5]));
* System.out.println("5 vs 0 : " + isConnected(arr[5], arr[0]));
*/
if (DBG) {
System.out.println(isConnected(0, 1));
System.out.println(isConnected(1, 0));
}
Queue<Integer> Q = new LinkedList<>();
int cnt = 0;
for (int i = 0; i <= N; i++) {
if (visited[i])
continue;
Q.offer(i);
visited[i] = true;
while (!Q.isEmpty()) {
int size = Q.size();
for (int q = 0; q < size; q++) {
int current = Q.poll();
for (int next = 0; next <= N; ++next) {
if (visited[next] || next == current)
continue;
if (!isConnected(current, next))
continue;
if (DBG)
System.out.printf("[%d %d] connected cnt: %d \n", current, next, cnt);
visited[next] = true;
Q.offer(next);
}
}
}
cnt++;
}
// 예제 입력 3에서 총 3개의 그룹을 그렸으므로 PU는 두 번이다.
System.out.println(cnt - 1);
}
private static boolean isConnected(int cur, int next) {
Rect c = arr[cur];
Rect n = arr[next];
if((c.sx < n.sx && n.ex < c.ex && c.sy < n.sy && n.ey < c.ey)
|| (c.sx > n.sx && n.ex > c.ex && c.sy > n.sy && n.ey > c.ey)
|| c.ex < n.sx || c.sx > n.ex || c.ey < n.sy || c.sy > n.ey )
return false;
return true;
}
/*
private static boolean isConnected(Rect base, Rect target) {
int[] dx = { target.sx, target.sx, target.ex, target.ex };
int[] dy = { target.sy, target.ey, target.ey, target.sy };
// 사각형의 4점중 하나라도 포함되는 경우 true 리턴
int cnt = 0;
for (int i = 0; i < 4; i++) {
if (dx[i] >= base.sx && dx[i] <= base.ex && dy[i] >= base.sy && dy[i] <= base.ey) {
cnt++;
}
}
// 4점이 모두 포함되는 경우, 시점과 종점이 같아야 한다.
if (cnt == 4) {
if (!base.equals(target)) {
return false;
}
return true;
}
if (cnt > 0)
return true;
return false;
}
*/
}
class Rect {
int sx, sy;
int ex, ey;
Rect(int sx, int sy, int ex, int ey) {
this.sx = sx;
this.sy = sy;
this.ex = ex;
this.ey = ey;
}
}