[SWEA 5987] 달리기 (JAVA)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWaJ4g86WA4DFAUQ

SW Expert Academy

1. 주의할 점

- 위상정렬과 관련된 문제처럼 보이지만 DP와 관련된 문제다(메모라이즈 기법 사용)

- DFS -> 시간초과

- 선수들은 1번부터 Node번호까지 있다

- 비트연산을 할 줄 모르면 고생한다(내가 그 예시다. 비트연산을 사용하지 않고도 할 수는 있지만 되게 더럽고 복잡해보인다. 그 시간에 비트연산을 공부하자)

 

2. 구현

- 첫 번째 접근: 위상정렬

  위상정렬 알고리즘을 이용하면 들어오는 순서를 찾을 수 있지만, 몇가지의 경우가 가능한지 알 수 없다.

- 두 번째 접근: 일반 DFS + 나름의 그리디?

  DFS만 사용하면 16! 하지만 선두로 필요로 하는 선수가 모두 나와있다면 다음 선수 진행하는 방식으로 진행 

  결과: 시간초과

- 세 번째 접근: DFS + DP(메모라이즈)

  하지만 DFS를 통해 어떻게 나타낼것인가? -> 2진수로 표현해서 다 해당 선수들의 index만큼 다 더한다 -> 나중에 어떤 선수가 나왔는지 정확히 어떻게 알 것인가? -> 비트마스킹 쓴다

우선 해당 선수가 뛸라면 어떤 선두 선수들을 필요로 하는가 : li[]배열로 비트마스킹을 이용해서 표현

DFS 함수내에서 전체 선수가 다 뛰었는지 확인하는 과정 : if(idx==(1<<(node+1))-2) 

같은 번호들의 선수가 이미 뛴 적이 있는 경우 : if(dp[idx]!=0) -> 메모라이즈

나머지는 코드의 주석을 살펴보면 이해하기 쉽다.

  

 

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

public class Solution_d4_5987_달리기 {
	static int node,edge;
	static long dp[],li[];		//16자리를 2진수로 바꿔서 생각 최대 2^17, 해당 선수가 들어오려면 어떤 선수들이 선두로 들어와 있어햐는지
	
	static long dfs(int idx) {		// 지금까지 누가 들어왓는지
		if(idx==(1<<(node+1))-2) return 1;
		if(dp[idx]!=0) return dp[idx];
		
		for(int i=1;i<=node;i++) {
			if((idx & 1<<i)>0)		//이미 해당 선수가 들어온 경우
				continue;
			if((idx & li[i])!=li[i]) continue;		//선두로 나와야하는 선수들이 아직 다 나오지 않은 경우
			dp[idx]+=dfs(idx|1<<i);
		}
		return dp[idx];
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int test = Integer.parseInt(br.readLine().trim());
		for(int t=1;t<=test;t++) {
			String s = br.readLine();
			StringTokenizer st = new StringTokenizer(s);
			node = Integer.parseInt(st.nextToken());
			edge = Integer.parseInt(st.nextToken());
			//초기화
			li = new long[node+1];
			dp = new long[1<<(node+1)];
			
			int start,end;
			for(int i=0;i<edge;i++) {
				String str = br.readLine();
				StringTokenizer st2 = new StringTokenizer(str);
				start = Integer.parseInt(st2.nextToken());
				end = Integer.parseInt(st2.nextToken());
				li[end] = li[end]|1<<start;		//선두에 있어야하는 선수들
			}				
			System.out.println("#"+t+" "+dfs(0));
		}	
	}
}