[백준] 멀티버스 1 18868번 [JAVA]

출처 : https://www.acmicpc.net/problem/18868

18868번: 멀티버스 Ⅰ

문제

M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2, ..., AN, 우주 B에 있는 행성의 크기는 B1, B2, ..., BN라고 하자. 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

입력

첫째 줄에 우주의 개수 M과 각 우주에 있는 행성의 개수 N이 주어진다. 둘째 줄부터 M개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

제한

• 2 ≤ M ≤ 10
• 3 ≤ N ≤ 100
• 1 ≤ 행성의 크기 ≤ 10,000

풀이방법

- "조합" 을 이용해서 M 개 우주의 쌍 중에서 2개를 선택한다.

- 균등한지 평가하도록 하는 조건을 IsSimilar 함수를 만들어서 처리한다.

- 조합을 활용하면 어렵지 않게 풀 수 있는 문제였다.

코드

import java.util.Scanner;

public class Main {

	static int M, N; // M : row , N : column
	static int[][] score;
	static boolean[] visited;
	static int answer = 0;
	static int[] sel = new int[2];
	static int selected_idx = 0;

	static void perm(int idx, int s_idx) {
		if (s_idx > 2)
			return;
		// 2개 골랐다면
		if (idx == M) {
			if (s_idx == 2) {
				for (int i = 0; i < M; i++) {
					if (visited[i]) { // 2개의 쌍 골랐다. !
						sel[selected_idx++] = i; // 각 번호저장
					}
				}

				if (IsSimilar(sel[0], sel[1])) // 첫번째 반 학생들과, 두번째 반학생들이 실력이 비슷한지? 호출
					answer++;
				selected_idx = 0; // 초기화
				return;
			} else {
				return;
			}
		}

		if (!visited[idx]) {

			visited[idx] = true;
			perm(idx + 1, s_idx + 1);
			visited[idx] = false;
			perm(idx + 1, s_idx);
		}

	}

	// 제공된 공식에 부합한지 체크하는 함수
	private static boolean IsSimilar(int i, int j) {

		for (int rear = 0; rear < N; rear++) { // 처음 위치 부터 검사하면서 == rear
			for (int head = rear + 1; head < N; head++) { // rear 다음부터 == head

				// 첫 번째 반들과 과 두번 째 반들의 rear번째와 head 번째의 관계가 적합한지 체크
				if (compare(score[i][rear], score[i][head]) != compare(score[j][rear], score[j][head])) {
					return false;
				}
			}
		}

		return true;
	}

	// i번째, j번쨰의 크기 비교
	private static int compare(int i, int j) {
		if (i < j)
			return 1;
		else if (i == j)
			return 0;
		else
			return -1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();

		score = new int[M][N];
		visited = new boolean[M]; // M개의 학급에 대해 방문 처리를 할것이기 때문에 우선

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				score[i][j] = sc.nextInt();

			}
		}

		// 조합 사용해서 2개의 반씩 모든 쌍 구하고
		perm(0, 0);
		System.out.println(answer);

	}

}