글 읽기 - BFS를 DFS로 바꿨는데 어디서 틀리는지 모르겠네요..ㅠㅠ

jaeuk9407 3년 전 0

BFS로 한 번 풀어서 맞고, DFS로 변환해서 풀어봤는데 계속 틀렸다고 하는데 이것저것 돌려봐도 반례를 못찾겠네요..

도움을 구합니다 ㅠㅠ..

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

public class Main {
	static int N, cnt, flags[]; 
	static Info_P3108_2[] recs;
	static boolean[] visited;
	
	private static void dfs(int start, int flag) {
		
		// 방문하지 않은 경우에만 수행
		if(visited[start]) {
			return; 
		}
		
		visited[start] = true;
		flags[start] = flag;
		
		for(int i = 0; i <= N; i++) {
			// 현재 사각형과 접점이 있다면 간다.
			// 비교 대상은 1) 자기 자신 제외, 2) 방문 X
			if(start != i && !visited[i]) {
				// 접점이 있는지 확인
				if(check(start, i)) {
					dfs(i, flag);
				}
			}
		}
	}
	
	private static boolean check(int rec1, int rec2) {
		Info_P3108_2 r1 = recs[rec1];
		Info_P3108_2 r2 = recs[rec2];
		

		// r1이 r2를 내포하는 경우 => 접점 존재 X
		if(r1.x1 < r2.x1 && r2.x2 < r1.x2 && r1.y1 < r2.y1 && r2.y2 < r1.y2) {
			return false;
		}
		// r2가 r1을 내포하는 경우 => 접점 존재 X
		if(r2.x1 < r1.x1 && r1.x2 < r2.x2 && r2.y1 < r1.y1 && r1.y2 < r2.y2) {
			return false;
		}
		// 접점이 존재하지 않는 경우
		if(r1.x2 < r2.x1 || r1.y2 < r2.y1 || r2.x2 < r1.x1 || r2.y2 <r1.y1) {
			return false;
		}
		
		
		// 접점이 반드시 존재
		return true;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		recs = new Info_P3108_2[N+1];
		visited = new boolean[N+1];
		flags = new int[N+1];
		
		recs[0] = new Info_P3108_2(0, 0, 0, 0);
		
		for(int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			Info_P3108_2 rec = new Info_P3108_2(x1, y1, x2, y2);
			recs[i] = rec;
		}
		
		for(int i = 0; i <= N; i++) {
			dfs(i, i);
		}
		
		for(int i = 0; i < N; i++) {
			if(flags[i] != flags[i+1]) {
				cnt++;
			}
		}
//		System.out.println(Arrays.toString(flags));
		System.out.println(cnt);
	}

}


class Info_P3108_2{
	int x1, y1, x2, y2;

	public Info_P3108_2(int x1, int y1, int x2, int y2) {
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
	}
	@Override
	public String toString() {
		return "[x1=" + x1 + ", y1=" + y1 + ", x2=" + x2 + ", y2=" + y2 + "]";
	}
}

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

문제

문제

출처

ICPC

BFS를 DFS로 바꿨는데 어디서 틀리는지 모르겠네요..ㅠㅠ

jaeuk9407 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말