[백준 Silver 3] 15270 친구 팰린드롬 - Java

문제링크 : https://www.acmicpc.net/problem/15270

15270번: 친구 팰린드롬

 

접근 과정 : 

• 반 친구들은 1:1로 묶여져야 한다.
• 관계도의 조합을 만들어가고, 각 조합에 따라 친구의 사용 유무를 확인하여 가능한 최대수를 찾는다!!
• 최대한 세울 수 있는 친구 수가 N보다 작다면, 1명을 추가!!

 

소스 코드 및 결과 : 

package BOJ;

import java.io.*;
import java.util.*;

/* 
    친구 팰린드롬

*/
public class BOJ15270 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        friends = new int[M][2];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            friends[i][0] = Integer.parseInt(st.nextToken());
            friends[i][1] = Integer.parseInt(st.nextToken());
        }

        max = 0;
        visit = new boolean[N + 1];

        find(0, 0);

        max *=2;

        if (max < N) {
            max++;
        }

        System.out.println(max);

    }

    static int N, M, max;
    static int[][] friends;
    static boolean[] visit;

    static void find(int index, int count) {

        if (index >= M) {
            max = Math.max(max, count);
            return;
        }

        if (visit[friends[index][0]] || visit[friends[index][1]]) {
            find(index + 1, count);
        } else {
            visit[friends[index][0]] = true;
            visit[friends[index][1]] = true;

            find(index + 1, count + 1);

            visit[friends[index][0]] = false;
            visit[friends[index][1]] = false;

            find(index + 1, count);
        }

    }

}