글 읽기 - 로고 질문드립니다.

shpre1236 7년 전 0

dfs로 돌리면 된다고 하는데 왜 틀렸는지 잘 모르겠습니다.

혹시나 겹치는 조건이 잘못되었나하고 질문에 올라온 코드도 붙여보았는데 안되네요.

어디서 제가 놓치고 있는걸까요?

public class p3108{
	static int[][] pt;
	static int N;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		pt = new int[N][4];
		for(int i=0; i<N; i++){
			int t0 = sc.nextInt();
			int t1 = sc.nextInt();
			int t2= sc.nextInt();
			int t3 = sc.nextInt();
			pt[i][0] = Math.min(t0, t2);
			pt[i][1] = Math.min(t1, t3);
			pt[i][2] = Math.max(t0, t2);
			pt[i][3] = Math.max(t1, t3);
		}
		
		visit = new boolean[N];
		int result = 0;
		for(int i=0; i<N; i++){
			if(!visit[i]){
				dfs(i);
				result++;
				// System.out.println(i);
			}
		}
		System.out.println(result);
	}
	
	static boolean[] visit;
	static void dfs(int now){
		visit[now] = true;
		for(int i=0; i<N; i++){
			if(visit[i])	continue;
			if(pt[now][0] < pt[i][0] && pt[i][2] < pt[now][2] && pt[now][1] < pt[i][1] && pt[i][3] < pt[now][3])
				continue;
			if(pt[now][0] > pt[i][0] && pt[i][2] > pt[now][2] && pt[now][1] > pt[i][1] && pt[i][3] > pt[now][3])
				continue;
			if(pt[i][0] > pt[now][2] || pt[i][2] < pt[now][0] ||
					pt[i][1] > pt[now][3] || pt[i][3] < pt[now][1])
				continue;
			
			dfs(i);
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

로고 질문드립니다.

shpre1236 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말