[HSAT 2회 정기 코딩 인증평가 기출] 사물인식 최소 면적 산출 프로그램 *

사용 알고리즘: dfs

사용 언어: java

 

 

시간초과

package week15;

import java.io.*;
import java.util.*;

public class Main_softeer_사물인식최소면적 {
	static int n, k, answer = 2000*2000; //제약조건
	static List<int[]> colors[];

	public static void main(String[] args) throws IOException {
		input_사물인식최소면적();
		
		for(int[] start : colors[0]) {
			//색깔, 가장작은좌표, 가장큰좌표
			dfs_사물인식최소면적(1, start[0],start[1], start[0],start[1]);
		}
		
		System.out.println(answer);
	}

	private static void dfs_사물인식최소면적(int num, int minX, int minY, int maxX, int maxY) {
		int area = (maxX - minX) * (maxY - minY);
				
		//종료 조건 1. 모든 색깔을 포함했으면, 작은 넓이 값으로 갱신
		if(num == k) {
			answer = Math.min(answer, area);
			return;
		}
		
		//돌아
		for(int[] cur : colors[num]) {
			int x1 = Math.min(cur[0], minX);
			int x2 = Math.max(cur[0], maxX);
			
			int y1 = Math.min(cur[1], minY);
			int y2 = Math.max(cur[1], maxY);
			
			dfs_사물인식최소면적(num+1, x1,y1, x2,y2);
		}
	}

	private static void input_사물인식최소면적() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken()); //점 개수
		k = Integer.parseInt(st.nextToken()); //색깔 개수
		
		colors = new ArrayList[k]; //색깔에 맞춰, 좌표 인풋~
		for (int i = 0; i < k; i++) {
			colors[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int color = Integer.parseInt(st.nextToken()) - 1;
			
			colors[color].add(new int[] {x, y});
		}
	}	

}

 

 

하...

일단 color 별로 list 만들어서 입력 받아야 한다는 아이디어는 냈다.

근데 그 이후에 깔라 별로 dfs 돌리는 미친 아이디어를 생각해내지 못했다.

 

아이디어를 알고 보면 그다지 어려울 것도 없는 문제였는데...

왜 떠올리지 못했을까? 슬프다... 하지만 정답률이 20%대니까 어려운 게 맞았나보다. 기쁘다^^

 

근데 그 와중에 시간초과는 또 뭐지 슬프다...

 

 

시간초과 일부 해결

import java.io.*;
import java.util.*;

public class Main {
	static int n, k, answer = 2000*2000; //제약조건
	static List<int[]> colors[];

	public static void main(String[] args) throws IOException {
		input_사물인식최소면적();
		
		for(int[] start : colors[0]) {
			//색깔, 가장작은좌표, 가장큰좌표
			dfs_사물인식최소면적(1, start[0],start[1], start[0],start[1]);
		}
		
		System.out.println(answer);
	}

	private static void dfs_사물인식최소면적(int num, int minX, int minY, int maxX, int maxY) {
		int area = (maxX - minX) * (maxY - minY);
				
		//종료 조건 1. 모든 색깔을 포함했으면, 작은 넓이 값으로 갱신
		if(num == k) {
			answer = Math.min(answer, area);
			return;
		}

        //종료 조건 2. 크기가 크면 말자
        if(area > answer) return;
		
		//돌아
		for(int[] cur : colors[num]) {
			int x1 = Math.min(cur[0], minX);
			int x2 = Math.max(cur[0], maxX);
			
			int y1 = Math.min(cur[1], minY);
			int y2 = Math.max(cur[1], maxY);
			
			dfs_사물인식최소면적(num+1, x1,y1, x2,y2);
		}
	}

	private static void input_사물인식최소면적() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken()); //점 개수
		k = Integer.parseInt(st.nextToken()); //색깔 개수
		
		colors = new ArrayList[k]; //색깔에 맞춰, 좌표 인풋~
		for (int i = 0; i < k; i++) {
			colors[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int color = Integer.parseInt(st.nextToken()) - 1;
			
			colors[color].add(new int[] {x, y});
		}
	}	

}

 

//종료 조건2.를 추가해서 일부 시간 초과 문제를 해결했으나, 여전히 3개의 subTask에서 시간 초과 발생

===> dfs를 넣기 전에 미리 넓이를 계산하고 dfs를 진행 할지 말지 정해보자

 

 

맞은 답

import java.io.*;
import java.util.*;

public class Main {
	static int n, k, answer = 2000*2000; //제약조건
	static List<int[]> colors[];

	public static void main(String[] args) throws IOException {
		input_사물인식최소면적();
		
		for(int[] start : colors[0]) {
			//색깔, 가장작은좌표, 가장큰좌표
			dfs_사물인식최소면적(1, start[0],start[1], start[0],start[1]);
		}
		
		System.out.println(answer);
	}

	private static void dfs_사물인식최소면적(int num, int minX, int minY, int maxX, int maxY) {
		int area = (maxX - minX) * (maxY - minY);
				
		//종료 조건 1. 모든 색깔을 포함했으면, 작은 넓이 값으로 갱신
		if(num == k) {
			answer = Math.min(answer, area);
			return;
		}

		
		//돌아
		for(int[] cur : colors[num]) {
			int x1 = Math.min(cur[0], minX);
			int x2 = Math.max(cur[0], maxX);
			
			int y1 = Math.min(cur[1], minY);
			int y2 = Math.max(cur[1], maxY);

            //종료 조건 대신, 여기서 넓이 계산 후, answer보다 작을 때만 다음 step으로 넘어가기
            int nxtArea = (x2-x1) * (y2-y1);
            if(nxtArea < answer) {
                dfs_사물인식최소면적(num+1, x1,y1, x2,y2);
            }
		}
	}

	private static void input_사물인식최소면적() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken()); //점 개수
		k = Integer.parseInt(st.nextToken()); //색깔 개수
		
		colors = new ArrayList[k]; //색깔에 맞춰, 좌표 인풋~
		for (int i = 0; i < k; i++) {
			colors[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int color = Integer.parseInt(st.nextToken()) - 1;
			
			colors[color].add(new int[] {x, y});
		}
	}	

}