์น๊ตฌ ์ฌ๋ถ๋ฅผ ์ค ๋, ์น๊ตฌ์ธ ์ ๋ค๋ผ๋ฆฌ๋ง ์ง ์ง์ด์ค์ผํจ
์ ๋ ฅ
Case(c)
์ฌ๋์(n), ์น๊ตฌ ์(m)
์น๊ตฌ์ธ ์ฌ๋ ๋์ด
์ถ๋ ฅ
์ง ์ง์ ์ ์๋ ๋ฐฉ๋ฒ์ ์ดํฉ
๐ก ์น๊ตฌ ์์ ์ ์ฅํ๋ 2์ฐจ์ ๋ฐฐ์ด
๐ก ์ด๋ฏธ ์ง์ด ์ ํด์ก๋์ง๋ฅผ ํ๋ณํ๋ 1์ฐจ์ ๋ฐฐ์ด
๐ก ์ง์ ์ ํ๋ ์กฐํฉ๋ฌธ์ : ์ฌ๊ทํจ์ ์ฌ์ฉ
1) ์น๊ตฌ ์ฌ๋ถ๋ฅผ ๋ฐ์์ ์ ์ฅ
boolean friends[][] = new boolean[n][n];
friends[x][y] = true;
2) ์ง์ด ์ ํด์ก๋์ง ํ๋ณํ๋ ๋ฐฐ์ด ์์ฑ
boolean taken[] = new boolean[n];
3) ์ฌ๊ทํจ์ ์ด์ฉํ dfs ๊ตฌํ
taken[pairOne] = taken[pairTwo] = true;
dfs(taken);
taken[pairOne] = taken[pairTwo] = false;
import java.util.*;
public class Picnic {
static int c,n,m;
static boolean friends[][] = new boolean[10][10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
c = sc.nextInt();
int result[] = new int[c];
for(int i=0; i<c; i++) {
n = sc.nextInt();
m = sc.nextInt();
boolean taken[] = new boolean[n];
for(int j=0; j<m; j++) {
int x = sc.nextInt();
int y = sc.nextInt();
friends[x][y] = true;
friends[y][x] = true;
}
result[i] = count(taken);
}
for(int i=0; i<c; i++)
System.out.println(result[i]);
sc.close();
}
public static int count(boolean taken[]) {
int pairOne = -1;
for(int i=0; i<n; i++) {
if(!taken[i]) {
pairOne = i;
break;
}
}
if(pairOne == -1)
return 1;
int ret = 0;
for(int pairTwo=pairOne+1; pairTwo<n; pairTwo++) {
if(!taken[pairTwo] && friends[pairOne][pairTwo] == true) {
taken[pairTwo] = true;
taken[pairOne] = true;
ret += count(taken);
taken[pairTwo] = false;
taken[pairOne] = false;
}
}
return ret;
}
}
ํ๋ฆผ ใ ...