백준 15270번 친구 팰린드룸 (JAVA)

https://www.acmicpc.net/problem/15270

15270번: 친구 팰린드롬

 

저는 dfs를 통해 문제를 해결하였습니다.

dfs를 진행하면서 해당 뎁스의 친구와 다른 친구와 같이 춤을 추게 맺어주고, 총 맺어진 친구의 수를 구하였습니다.

여기서 아무도 친구 관계가 아니라면, 혼자 올라갈 수 있기 때문에 result = 1로 초기화하였습니다.

마지막으로 총 맺어진 친구의 수가 n보다 작다라는건 센터에 아무도 친구로 맺어지지 않은 친구를 세울 수 있기 때문에 하나 증가시켜서 리턴하여 문제를 해결하였습니다.

 

package BOJ.dfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_15270 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        List<Integer>[] friend = new List[n+1];
        for(int i = 0 ; i <= n ; i++){
            friend[i] = new LinkedList<>();
        }
        for(int i = 0 ; i < m ; i++){
            st = new StringTokenizer(br.readLine());
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            friend[a].add(b);
            friend[b].add(a);
        }
        boolean[] used = new boolean[n+1];
        int result = cal(1,friend,used,n);
        System.out.println(result);
    }

    private static int cal(int depth, List<Integer>[] friend, boolean[] used,int n) {
        if(depth > n){
            int cnt = 0;
            for(int i = 1 ; i <= n ; i++){
                if(used[i]){
                    cnt++;
                }
            }
            if(cnt < n){
                cnt++;
            }
            return cnt;
        }
        int result = 1;
        result = Math.max(result, cal(depth+1,friend,used,n));
        if(used[depth]){
            return result;
        }
        used[depth] = true;
        for(int next : friend[depth]){
            if(used[next]){
                continue;
            }
            used[next] = true;
            result = Math.max(result, cal(depth+1,friend,used,n));
            used[next] = false;
        }
        used[depth] = false;
        return result;
    }
}