백준 9205. 맥주 마시면서 걸어가기 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/9205

"가지치기, 플로이드워셜"

풀다가 시간초과가 났다. 가지치기나 DP 등이 필요할거 같다는 생각이 들었고, 갈수 있냐 없냐의 문제였음.

그냥 특정 지점에 맥주를 가장 많이 들고 간 경우만 지나갈 수 있게 해줬다...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
    
    static int T;
    static int n;
    static int[][] adj;
    static int[] dp;
    static boolean find;
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        
        while(T-- > 0) {
            n = Integer.parseInt(br.readLine());
            adj = new int[n+2][n+2];
            find = false;
            dp = new int[n+2];
            
            Arrays.fill(dp, -1);
            
            int[][] temp = new int[n+2][2];
            
            for (int i = 0; i < n+2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                temp[i][0] = Integer.parseInt(st.nextToken());
                temp[i][1] = Integer.parseInt(st.nextToken());
            }
            
            for (int i = 0; i < n+2; i++) {
                for (int j = 0; j < n+2; j++) {
                    if( i == j ) continue;
                    
                    adj[i][j] = Math.abs(temp[i][0] - temp[j][0]) 
                            + Math.abs(temp[i][1] - temp[j][1]); 
                }
            }
            
            if(adj[0][n+1] <= 1000) {
                System.out.println("happy");
                continue;
            }
            
            dp[0] = 1000;
            solve(0,1000);
            System.out.println(find ? "happy" : "sad");
        }
        
    }
 
    static void solve(int cur, int avail) {
        if(find) return ;
        
        if(cur == n+1) {
            find = true;
            return ;
        }
        
        for (int i = 1; i < n+2; i++) {
            if(adj[cur][i] > avail || dp[i] >= avail)
                continue;
            
            dp[i] = avail;
            solve(i,1000);
        }
    }
}