친구 팰린드롬15270

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

BFS로 풀려고 했는데 실패...

찾아보고 참고해서 풀었다.

문제를 몇번이고 읽어도 이해가 되지 않았다. 특히
예제 20 0 입력의 답이 1이라는것도 이해가 되지 않았다.
그런데 풀이 소스코드를 읽고 이해해보려고 노력해보니 대략 이해가 되었다

이 문제는 그래프에서 연결된 노드들중에서 최대한 짝을 이룰수 있는 개수를 찾는것이다. 그리고 그러면 짝의개수X2 를 하면 무대에 오를 수 인원이 나온다. 그리고 무대에오를수 있는 인원 < 전체인원 이라면 1명을 추가할 수 있다. 왜 하필 한명만 추가할 수 있다는거지? 모두다 로봇춤을 추니까 그냥 다 올라갈 수 있는거 아냐? 부분이 이해가 안되었는데 문제에서 보면 일렬로 무대에 서있고 양쪽에서 한명씩 짝을 이룬다고 되어 있다. 근데 5명이 올라가는 경우도 있고 가운데에 1명만 남는경우도 가능하다고 말하고 있다.

즉 일단 짝을 이루는 인원이 무대에 올라가고(짝이 없는 경우 0명일것이다) + 1명은 짝을 이루지 못해도 올라갈수 있다는 의미이다.

짝을 이룬 인원이 == 전체인원 이라면 추가할 인원이 없다 하지만 짝을 이룬 인원이 < 전체인원 이라면 한명만 추가할 수 있다.

다시 정리해보자
1. 일단 짝을 이룰수 있는 최대 인원을 찾는다.
2. 최대인원이 < 전체인원 인경우 1명 추가할 수 있다.

얼핏 생각하면 연결된 노드개수가 무대에 올라갈 수 있는 인원 아닌가 싶어서 BFS로 풀 수 있지않나 해서 BFS 로 풀어보려 했지만 실패한 이유는 다음의 경우이다

위의 경우 최대 짝은 1개 밖에 나오지 않는다. 최대 올라갈 수 있는 인원은 2라서 전체인원 4보다 작으므로 +1 하면 답은 3이다
하지만 BFS로 시도하면 4가 나올것이다

혹시라도 1-4 이러게 짝을 이룰 수 있는거 아냐? 라고 생각했다면 문제를 잘못 이해한것이다. 위의 경우 짝을 이루는 경우는 1-2, 2-4, 2-3 의 3가지이므로 결국 하나의 짝만 이룰수 있다

import java.io.*;
import java.util.*;
public class Main {

    static int n;
    static int m;
    static int[][] friend;
    static boolean[] visit;

    static int answer;
    public static void main(String[] sdf) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        visit = new boolean[n+1];

        if (m == 0) {
            System.out.println(1);
            return;
        }

        friend = new int[m][2];

        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");

            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            friend[i][0] = a;
            friend[i][1] = b;
        }

        dfs(0, 0);

        answer *= 2;

        if(answer < n){
            answer++;
        }

        System.out.println(answer);
    }

    public static void dfs(int depth, int count){
       if(depth >= m){
           answer = Math.max(answer, count);
           return;
       }

       if(visit[friend[depth][0]] || visit[friend[depth][1]]){//둘중에 한명이 다른 짝이 있음
           dfs(depth+1, count);
       }else{
           visit[friend[depth][0]] = true;
           visit[friend[depth][1]] = true;

           dfs(depth+1, count+1);//짝을 이룬 경우 처리

           visit[friend[depth][0]] = false;
           visit[friend[depth][1]] = false;

           dfs(depth+1, count);//짝을 이루지 않을경우 처리
       }
    }
}