[종만북] GRADUATION - 졸업 학기 (자바 java)

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

목차

문제 : aoj-GRADUATION

 

풀이

   dfs나 bfs로 풀 수 있는 문제이다. 상당히 구현하기 까다로웠던 것 같다. 풀이는 주석으로 대신하는게 더 이해하기 좋을 것 같다.

...

private void solution() throws Exception {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int l = Integer.parseInt(st.nextToken());

    int[] pre = new int[n];	// pre[x]는 x번 과목의 선수과목을 비트마스킹 해둔 배열
    for (int i = 0; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        while (r-->0) pre[i] |= 1<<Integer.parseInt(st.nextToken());
    }

    int[] semester = new int[m];	// semester[x]는 x번 학기에 개설되는 과목을 비트마스킹 해둔 배열이다.
    for (int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        while (c-->0) semester[i] |= 1<<Integer.parseInt(st.nextToken());
    }

    Queue<Pos> q = new ArrayDeque<>();
    q.add(new Pos(0, 0, 0, 0));
    int answer = Integer.MAX_VALUE;

    while (!q.isEmpty()) {
        Pos cur = q.poll();

        if (cur.cnt >= k) {	// 현재까지 선택된 과목이 k개 이상이라면
            answer = Math.min(answer, cur.answer);	// 최소값을 갱신하며 답을 찾는다.
            continue;
        }
        if (cur.semesterIdx >= m) continue;	// m학기 넘게 진행되지 않게 처리한다.

        q.add(new Pos(cur.subject, cur.semesterIdx+1, cur.cnt, cur.answer));    // 이번학기 패스하는 경우

        List<Candidate> candidates = candidates(pre, n, l, cur.subject, semester[cur.semesterIdx]);
        for (Candidate next : candidates) {	// candidates는 현재 학기에서 최대한으로 들을 수 있는 과목들의 조합이다.
            if (next.cnt == 0) continue;

            int nextSubject = cur.subject|next.subjects;

            q.add(new Pos(nextSubject, cur.semesterIdx+1, cur.cnt+next.cnt, cur.answer+1));
            // 위에서 이번학기 패스하는 경우는 처리했고, 이번엔 이번학기에 특정 과목들을 듣는 경우이다.
        }
    }

    sb.append(answer == Integer.MAX_VALUE ? "IMPOSSIBLE" : answer).append('\n');
}

private List<Candidate> candidates(int[] pre, int n, int l, int subject, int semesterNum) {
    List<Integer> valid = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if ((semesterNum&1<<i) == 0 || (subject&1<<i) != 0 || !validPreSubject(n, pre[i], subject)) continue;

        valid.add(i);	// 현재 상황에서 듣는게 가능한 과목들을 valid에 넣어둔다.
    }

    List<Candidate> result = new ArrayList<>();
    if (valid.size() <= l) {	// 가능한 과목이 l 이하라면 무조건 듣는게 이득이다(그리디)
        int res = 0;
        for (Integer tmp : valid)
            res|=1<<tmp;
        result.add(new Candidate(res, valid.size()));
        return result;
    }

    choice(result, valid, l, 0, 0, 0);	
    // l 초과라면 가능한 과목들 중 l개를 선택하는 모든 경우를 확인한다. 
    // l개 미만은 무조건 손해이므로 무시한다.

    return result;
}

private void choice(List<Candidate> result, List<Integer> valid, int l, int cnt, int idx, int cur) {
    if (l-cnt > valid.size()-idx) return;   // 선택 가능한 수가 더 적은 경우 (백트래킹)
    if (cnt == l) {	// l개를 선택한 경우 후보군에 넣는다.
        result.add(new Candidate(cur, cnt));
        return;
    }

    choice(result, valid, l, cnt, idx+1, cur);	// 선택하지 않는 경우
    choice(result, valid, l, cnt+1, idx+1, cur|1<<valid.get(idx));	// 선택하는 경우
}

private boolean validPreSubject(int n, int pre, int subject) {	// 선수과목 체크용
    for (int i = 0; i < n; i++) {
        int pt = 1<<i;
        if ((pre&pt)!=0 && (subject&pt)==0) return false;
    }
    return true;
}

...

 

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }
    
    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());

        int[] pre = new int[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            while (r-->0) pre[i] |= 1<<Integer.parseInt(st.nextToken());
        }

        int[] semester = new int[m];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            while (c-->0) semester[i] |= 1<<Integer.parseInt(st.nextToken());
        }

        Queue<Pos> q = new ArrayDeque<>();
        q.add(new Pos(0, 0, 0, 0));
        int answer = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
            Pos cur = q.poll();

            if (cur.cnt >= k) {
                answer = Math.min(answer, cur.answer);
                continue;
            }
            if (cur.semesterIdx >= m) continue;

            q.add(new Pos(cur.subject, cur.semesterIdx+1, cur.cnt, cur.answer));    // 이번학기 패스하는 경우

            List<Candidate> candidates = candidates(pre, n, l, cur.subject, semester[cur.semesterIdx]);
            for (Candidate next : candidates) {
                if (next.cnt == 0) continue;

                int nextSubject = cur.subject|next.subjects;

                q.add(new Pos(nextSubject, cur.semesterIdx+1, cur.cnt+next.cnt, cur.answer+1));
            }
        }

        sb.append(answer == Integer.MAX_VALUE ? "IMPOSSIBLE" : answer).append('\n');
    }

    private List<Candidate> candidates(int[] pre, int n, int l, int subject, int semesterNum) {
        List<Integer> valid = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((semesterNum&1<<i) == 0 || (subject&1<<i) != 0 || !validPreSubject(n, pre[i], subject)) continue;

            valid.add(i);
        }

        List<Candidate> result = new ArrayList<>();
        if (valid.size() <= l) {
            int res = 0;
            for (Integer tmp : valid)
                res|=1<<tmp;
            result.add(new Candidate(res, valid.size()));
            return result;
        }

        choice(result, valid, l, 0, 0, 0);

        return result;
    }

    private void choice(List<Candidate> result, List<Integer> valid, int l, int cnt, int idx, int cur) {
        if (l-cnt > valid.size()-idx) return;   // 선택 가능한 수가 더 적은 경우
        if (cnt == l) {
            result.add(new Candidate(cur, cnt));
            return;
        }

        choice(result, valid, l, cnt, idx+1, cur);
        choice(result, valid, l, cnt+1, idx+1, cur|1<<valid.get(idx));
    }

    private boolean validPreSubject(int n, int pre, int subject) {
        for (int i = 0; i < n; i++) {
            int pt = 1<<i;
            if ((pre&pt)!=0 && (subject&pt)==0) return false;
        }
        return true;
    }
}

class Pos {
    int subject, semesterIdx, cnt, answer;

    public Pos(int subject, int semesterIdx, int cnt, int answer) {
        this.subject = subject;
        this.semesterIdx = semesterIdx;
        this.cnt = cnt;
        this.answer = answer;
    }
}

class Candidate {
    int subjects, cnt;

    public Candidate(int subjects, int cnt) {
        this.subjects = subjects;
        this.cnt = cnt;
    }
}

 

 

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