7568문제 덩치(완전탐색,브루트포스)+DFS로 변경해본 풀이추가

https://www.acmicpc.net/problem/7568

7568번: 덩치

 

풀이에 참고한 주소

https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-7568%EB%B2%88-%EB%8D%A9%EC%B9%98-%EC%9E%90%EB%B0%94Java

 

##포인트##

1. 완전탐색문제인데 어떻게 완전탐색을 할것인가
2. X,Y값으로 주어지는 몸무게,키를 어떻게 받을것인가
3. Rank가 어떻게 나뉘는가!

5
55 185
58 183
88 186
60 175
46 155

 

결국 각각 다 비교를 해서 자기보다 큰 덩치가 있는지 체크하면된다.

##일반적인 완전탐색 풀이##

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		//몸무게가 X고 키가Y면 그사람의 덩치는 (x,y)로 표시한다.
		//A,B가 있을때 X,Y값이 각각 더 크면 덩치가 더 크다라고 한다.
		
		//전체 사람의 수 N  조건 2 ≤ N ≤ 50
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int result[] = new int[N];
		//2중배열
		int[][] arr = new int[N][2];
 
		for(int i = 0; i < N; i++) {
			arr[i][0] = in.nextInt();	// [i][0] : 몸무게 
			arr[i][1] = in.nextInt();	// [i][1] : 키 
		}
		
		//모든사람과다 비교해서 자기보다 X,Y가 큰사람(덩치가 큰 사람이 있는지를 찾는다)
		for(int i=0; i<N; i++) {
			int rank = 1;
			for(int j=0; j<N; j++) {
				if(i==j) {
					result[i] = rank;
					continue;
				}else if(arr[i][0]<arr[j][0] && arr[i][1]<arr[j][1]) {
					rank++;
				}
				//마지막 비교대상인경우
				if(j+1==N) {
					result[i] = rank;
				}
			}
		}
		String sys = "";
		for(int i=0; i<result.length; i++) {
			if(i==0) {
				sys+= result[i];
			}else {
				sys+= " "+result[i];
			}
		}
		System.out.println(sys);

	}

}

 

##DFS로 변경해본 코드 완전탐색의 경우 dfs를 사용하기도 한다.##

import java.util.Scanner;

public class boj_7568_dfs {

	public static void main(String[] args) {
		//몸무게가 X고 키가Y면 그사람의 덩치는 (x,y)로 표시한다.
		//A,B가 있을때 X,Y값이 각각 더 크면 덩치가 더 크다라고 한다.
		
		//전체 사람의 수 N  조건 2 ≤ N ≤ 50
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int result[] = new int[N];
		//2중배열
		int[][] arr = new int[N][2];
 
		for(int i = 0; i < N; i++) {
			arr[i][0] = in.nextInt();	// [i][0] : 몸무게 
			arr[i][1] = in.nextInt();	// [i][1] : 키 
		}
		int depth =0; //최초 뎁스 0으로 시작 for문을 위해
		int length = N;
		for(int i=0; i<length; i++) {
			dfs(i,length,result,arr);	
		}

	}
	private static void dfs(int depth,int length,int[] result,int[][] arr) {
			//모든사람과다 비교해서 자기보다 X,Y가 큰사람(덩치가 큰 사람이 있는지를 찾는다)
			int rank = 1;
			for(int j=0; j<length; j++) {
				if(depth==j) {
					result[depth] = rank;
					continue;
				}else if(arr[depth][0]<arr[j][0] && arr[depth][1]<arr[j][1]) {
					rank++;
				}
				//마지막 비교대상인경우
				if(j+1==length) {
					result[depth] = rank;
				}
			}
		}
		
	}