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

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

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

1. 유형

조합, 브루트포스

 

2. 문제 접근

 

조합을 두 가지 방법으로 구현했습니다.

 

• 선택을 하고, 안 하는 것을 나타내는 함수 2번 호출

• 중복 선택을 for문을 통해서 막는 방법

i를 선택했을 경우 그 전 보다 1크게 for문을 시작하기 때문에 중복이 될 수 없음.

3. 코드

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

public class Main {
	static int N, M, map[][], count = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		boolean visit[] = new boolean[N + 1];
		map = new int[N + 1][N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int u = stoi(st.nextToken());
			int v = stoi(st.nextToken());
			map[u][v] = 1;
			map[v][u] = 1;
		}
		dfs(1, 0, new int[3]);
		System.out.println(count);
	}

	static void dfs(int val, int selidx, int sel[]) {
		if(selidx == 3) {
			if(map[sel[0]][sel[1]]==1 || map[sel[1]][sel[2]]==1 || map[sel[0]][sel[2]]==1) 
				return;
			count++;
			return;
		}
		if(val == N+1)
			return;
		sel[selidx] = val;
		dfs(val+1, selidx+1, sel);
		dfs(val+1, selidx, sel);
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}

 

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

public class Main {
	static int N, M, map[][], count = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		map = new int[N + 1][N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int u = stoi(st.nextToken());
			int v = stoi(st.nextToken());
			map[u][v] = 1;
			map[v][u] = 1;
		}
		dfs(0, new int[3], 1);
		System.out.println(count);
	}

	static void dfs(int saveIdx, int save[], int start) {
		if (saveIdx == 3) {
			if (map[save[0]][save[1]] == 1 || map[save[1]][save[2]] == 1 || map[save[0]][save[2]] == 1)
				return;
			count++;
			return;
		}
		for (int i = start; i <= N; i++) {
			save[saveIdx] = i;
			dfs(saveIdx + 1, save, i + 1);
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}