[종만북] PICNIC - 소풍 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-PICNIC

 

 

풀이

  n명을 일렬로 놓는 경우의 수는 n! 이다. 따라서 일렬로 놓고 2명씩 쌍을 짓는다고 생각해보면 O(C x n!)가 필요하므로 통과할 수 없다.

 

  더 효율적으로 하려면 2명씩 짝지어볼 수 있다. 이 때, 주의할 점은 아래의 경우들은 모두 같은 경우라는 점이다. '일부만 다르더라도 다른 방법' 이라고 써져 있는 부분은 짝이 다를 경우이지, 이미 정해진 쌍에 대해서는 상관이 없다.

• (0, 1), (2, 3)
• (0, 1), (3, 2)
• (1, 0), (2, 3)
• (2, 3), (0, 1)
• (3, 2), (1, 0)
• ... 등

 

  그리고 모든 학생이 쌍에 포함되어야 하므로, 그냥 쌍을 지어주는 방향을 고정시켜도 결과는 동일하다. n/2 개의 쌍을 모두, 쌍 중 좌측 학생의 번호가 증가하는 방향으로만 생각해보자. 또한 쌍 내에서도 좌측보다 우측 학생이 번호가 크게 만들자. 즉 위의 경우들 중에서는 (0, 1), (2, 3) 만 사용하겠다는 것이다.

 

  그렇게되면 n=10이라 할 때, 처음 시작은 무조건 0번 학생이고 (1가지), 고를 수 있는 짝은 9명이다. 2명이 이미 쌍으로 지정되었으므로 그 다음 학생은 아직 선택되지 않은 번호가 가장 낮은 학생이고 (1가지), 고를 수 있는 짝은 7명이다. 즉 총 O(C x (n-1) x (n-3) x ... x 1)으로 구할 수 있다. 이미 선택되지 않은 학생을 체크하기 위해서는 내 경우엔 비트 마스킹을 사용했다.

for (int i = startIdx; i < n; i++) {
    if ((v & (1 << i)) != 0) continue;	// 아직 선택되지 않은 가장 낮은 번호 학생을 선택
    v |= 1 << i;
    for (int next : edges[i]) {	// 짝이 될 학생을 고른다.
        if (next < i) continue;	// 방향 고정용
        if ((v & (1 << next)) != 0) continue;
        v |= 1 << next;
        search(idx + 1, i + 1);
        v ^= 1 << next;
    }
    v ^= 1 << i;
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private int n, cnt, v;
    private List<Integer>[] edges;

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine().trim());
        Main main = new Main();

        StringBuilder answer = new StringBuilder();
        while (c-- > 0) {
            answer.append(main.solution()).append('\n');
        }
        System.out.print(answer);
    }

    private int solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        init(Integer.parseInt(st.nextToken()));
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
        }

        for (int i = 0; i < n; i++) {
            if (edges[i].isEmpty()) {
                return 0;
            }
        }
        search(0, 0);
        return cnt;
    }

    private void init(int num) {
        n = num;
        edges = new ArrayList[n];
        for (int i = 0; i < n; i++)
            edges[i] = new ArrayList<>();
        cnt = v = 0;
    }

    private void search(int idx, int startIdx) {
        if (idx == n / 2) {
            cnt++;
            return;
        }
        for (int i = startIdx; i < n; i++) {
            if ((v & (1 << i)) != 0) continue;
            v |= 1 << i;
            for (int next : edges[i]) {
                if (next < i) continue;
                if ((v & (1 << next)) != 0) continue;
                v |= 1 << next;
                search(idx + 1, i + 1);
                v ^= 1 << next;
            }
            v ^= 1 << i;
        }
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.