[Algorithm] ๐Ÿž์†Œํ’

HaJingJingยท2021๋…„ 3์›” 28์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
1/119

1. ๋ฌธ์ œ ํ•ด์„

์นœ๊ตฌ ์—ฌ๋ถ€๋ฅผ ์ค„ ๋•Œ, ์นœ๊ตฌ์ธ ์• ๋“ค๋ผ๋ฆฌ๋งŒ ์ง ์ง€์–ด์ค˜์•ผํ•จ

์ž…๋ ฅ

Case(c)
์‚ฌ๋žŒ์ˆ˜(n), ์นœ๊ตฌ ์ˆ˜(m)
์นœ๊ตฌ์ธ ์‚ฌ๋žŒ ๋‚˜์—ด

์ถœ๋ ฅ

์ง ์ง€์„ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์˜ ์ดํ•ฉ


2. ์•„์ด๋””์–ด

๐Ÿ’ก ์นœ๊ตฌ ์Œ์„ ์ €์žฅํ•˜๋Š” 2์ฐจ์› ๋ฐฐ์—ด
๐Ÿ’ก ์ด๋ฏธ ์ง์ด ์ •ํ•ด์กŒ๋Š”์ง€๋ฅผ ํŒ๋ณ„ํ•˜๋Š” 1์ฐจ์› ๋ฐฐ์—ด
๐Ÿ’ก ์ง์„ ์ •ํ•˜๋Š” ์กฐํ•ฉ๋ฌธ์ œ : ์žฌ๊ท€ํ•จ์ˆ˜ ์‚ฌ์šฉ


3. ํ’€์ด

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;

4. ์ฝ”๋“œ

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;
	}

}

5. ๊ฒฐ๊ณผ

ํ‹€๋ฆผ ใ…Ž...

profile
๐ŸŒฑ์ดˆ๋ณด ๊ฐœ๋ฐœ์ž๐ŸŒฑ

0๊ฐœ์˜ ๋Œ“๊ธ€