[JAVA] 백준 15270

 

 

15270번: 친구 팰린드롬

문제

재홍이네 반 친구들은 모두 자신과 친한 친구하고만 춤을 추고 싶어한다. 재홍이는 이번 학예회에 스케일 크게 해보고 싶기 때문에 최대한 많은 친구를 무대에 세우려고 한다. 친구 관계도가 주어졌을 때, 최대 몇 명을 무대로 올려보낼 수 있는지 구해서 재홍이에게 알려주자. 친구들은 출석번호로 나타내며, 1부터 시작해서 N까지 있다. 각 친구는 오로지 하나의 출석번호를 갖는다.

A와 B가 친한 친구고, B와 C가 친한 친구라고해서 반드시 A와 C가 친한 친구는 아니다. 로봇 댄스를 추는 친구를 제외한 무대에 올라가는 친구들은 모두 각자 자신과 친한 친구하고만 춤을 춰야한다. 또한 재홍이 반 친구들은 모두 로봇 댄스를 출 수 있다.

2명씩 짝지어서 남은 학생이 있는 경우에 로봇춤을 추게하면 된다.

풀이

처음에는 연결 그래프를 만들어서 DFS로 탐색하면서 최대 몇 명까지 춤을 출 수 있는지로 접근했다.

하지만 이런 탐색은 2명씩 짝지어야 하는 상황과 맞지 않았다.

좀 더 고민해보다가 이전에 백트래킹을 사용해서 씨앗을 심는 문제 (1527)에서 사용한 백트래킹에 착안해서 탐색 후 돌아왔을 때 다시 Visit을 제거하고를 반복해서 문제를 해결했다!

📌 엣지 리스트 만들기

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine() , " " );
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A.add(new Friend(a, b));
        }

입력을 받고 연결 그래프가 아닌 간선들의 리스트를 만들었다.

간선들을 차례차례 탐색하면서 최댓값을 찾아나가는 방식으로 구현했다.

📌 친구 관계 클래스 (엣지)

    static class Friend{
        int x;
        int y;
        public Friend(int x, int y){
            this.x = x;
            this.y = y;
        }

        public void check(){
            V[this.x] = !V[this.x];
            V[this.y] = !V[this.y];
        }

        public boolean isChecked(){
            return V[this.x] || V[this.y];
        }
    }

간선은 Friend로 나타냈다. 여기서 x와 y는 친구 관계이다.

• 각 정점(사람)의 방문여부를 수시로 변경할 것이기 때문에 check() 메서드를 구현했고 현재 친구 관계 중에서 한 명이라도 춤출사람이 정해진 사람이 있다면 짝지을 수 없기 때문에 isChecked() 메서드를 구현했다.

📌 짝지을 수 있는 인원의 최댓값을 구하는 메서드

    public static void search(int i, int value){
        Friend x = A.get(i);
        if(x.isChecked()) return;
        if(value > count) count = value;

        for(int j=i; j<A.size(); j++){
            x.check();
            search(j, value+2);
            x.check();
        }
    }

i : 엣지 리스트의 인덱스이다.

value : 현재까지 발견된 짝지은 인원이다.

엣지 리스트에 담긴 친구 관계를 돌면서 어디까지 짝을 지을 수 있는지 체크한다.

끝까지 탐색을 마치고 종료했다면 다시 친구 관계를 해제해준다. 즉, 탐색을 종료하면 방문 여부를 초기화해준다.

• 반복문의 j = i를 해준 이유는 이전에 방문했던 곳이기 때문에 굳이 더 탐색을 해줄 필요는 없다. (이 부분에서 시간 초과가 갈린다.)

📌 전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main {
    static ArrayList<Friend> A;
    static boolean[] V;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine() , " ");

        int N =Integer.parseInt(st.nextToken())+1;
        int M = Integer.parseInt(st.nextToken());

        A = new ArrayList<>();
        V = new boolean[N];

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine() , " " );
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            A.add(new Friend(a, b));
        }
        for(int i=0; i<A.size(); i++){
            search(i, 2);
        }

        System.out.println( count % 2 == 0&& count != N-1 ? count+1 : count);

    }

    public static void search(int i, int value){
        Friend x = A.get(i);
        if(x.isChecked()) return;
        if(value > count) count = value;

        for(int j=i; j<A.size(); j++){
            x.check();
            search(j, value+2);
            x.check();
        }
    }
    static class Friend{
        int x;
        int y;
        public Friend(int x, int y){
            this.x = x;
            this.y = y;
        }

        public void check(){
            V[this.x] = !V[this.x];
            V[this.y] = !V[this.y];
        }

        public boolean isChecked(){
            return V[this.x] || V[this.y];
        }
    }
}

결과

아직 완전 탐색이라는 문제에 감을 잡지못해서 굉장히 어려웠다.