[백준] 2422. 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (Java)

문제

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

 

알고리즘

브루트포스, 조합, 그래프

 

 

풀이

아이스크림이 수가 최대인 200일 때, 아이스크림을 고르는 경우의 수는 200C3 = 200 * 199 * 198 / 6 = 약 130만이다.

130만 개의 경우의 수마다 최대 10000개에 해당하는 섞어먹으면 안되는 조합을 일일이 검사하면 130만 * 1만으로 시간 초과가 난다.

따라서 2차원 배열로 그래프를 만들어 섞어먹으면 안되는 조합인지 O(1)에 알 수 있도록 한다.

 

[N+1][N+1] 크기의 2차원 배열 graph를 만들어

섞어먹으면 안되는 조합 a 와 b가 입력으로 주어지면 graph[a][b] 와 graph[b][a]를 1 (혹은 true) 로 변경한다.

 

이제 N개의 아이스크림 중 3개의 아이스크림을 a, b, c를 선택했을 때

graph[a][b], graph[b][c], graph[c][a] 가 모두 0 (혹은 false) 이라면 섞어먹어도 되는 조합임을 바로 알 수 있다.

 

코드

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

public class Main {
	static int N, answer, board[][], selected[];
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		selected = new int[3];
		board = new int[N + 1][N + 1];
		visited = new boolean[N + 1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			board[u][v] = 1;
			board[v][u] = 1;
		}

		answer = 0;
		comb(0, 1);
		System.out.println(answer);
	}

	private static void comb(int count, int start) {
		if (count == 3) {
			if(board[selected[0]][selected[1]] == 1 ||
				board[selected[1]][selected[2]] == 1 ||
				board[selected[2]][selected[0]] == 1)
				return;

			answer++;
			return;
		}

		for (int i = start; i <= N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				selected[count] = i;
				comb(count + 1, i + 1);
				visited[i] = false;
			}
		}
	}
}