[SWExpertAcademy]5987. 달리기

문제

풀이

dfs + dp문제
비트마스킹을 사용

코드

import java.io.*;
import java.util.*;
//SWEA 5987. 달리기
public class Solution {
	//완주자상태에 따른 경우의 수를 저장, 각 사람보다 먼저 완주해야 되는 사람들을 저장(비트마스킹 사용)
	static long dp[],player[];
	static int N;
	static long dfs(int cur) {
		//모든 사람이 완주한 경우
		if(cur==(1<<N+1)-2) return 1;
		//이미 연산을 한 케이스의 경우, 저장된 값 반환
		if(dp[cur]>0)return dp[cur];
		for(int i=1;i<=N;i++) {
			//i번째 사람이 아직 완주하지 않았고, i보다 먼저 완주해야 될 사람들이 완주 했을 경우
			if((cur&1<<i)==0&&(cur&player[i])==player[i]) {
				//i번째 사람을 완주 시킴
				dp[cur]+=dfs(cur|1<<i);
			}
		}
		return dp[cur];
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T=Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			int M=Integer.parseInt(st.nextToken());
			player=new long[N+1];
			dp=new long[1<<(N+1)];
			for(int i=0;i<M;i++) {
				st=new StringTokenizer(br.readLine());
				int x=Integer.parseInt(st.nextToken()),y=Integer.parseInt(st.nextToken());
				//y번째 사람이 완주하기 전에 x가 완주해야 함
				player[y]=player[y]|1<<x;
			}
			System.out.println("#"+t+" "+dfs(0));
		}
	}
}