[BOJ] 1941: 소문난 칠공주 (Java) with 조합

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

1941번: 소문난 칠공주

---

이전에 C++로 푼 문제이다. https://morenow.tistory.com/21

[BOJ] 1941: 소문난 칠공주 (C++) with 조합

Java로 조합을 경험해보기 위해 푼 문제이므로 시간은 의미가 없어서 적지 않았다.

나는 pseudo 코드로 거의 모든 코드를 작성한 후 문제를 푸는데, Java로 할 때는 pseudo 코드를 적는 속도가 너무 느리다... 기존에 알던 알고리즘도 메소드 이름 등이 헷갈리니까 생각에 제동이 걸리는 느낌..

알고리즘

알고리즘의 대부분은 위의 C++로 푼 게시글에 나와있다. 요약하자면 5 X 5 교실의 25명 중 7명을 조합해서, 붙어있는지 (adj 메소드) 그리고 이다솜파가 많은지 (moreDasom 메소드) 확인을 하고 카운트를 하면 된다.

이 때, 굳이 i와 j 두 개를 조합하지 않고, 하나만 뽑아 5로 나눈 몫과 나머지로 i와 j를 대체하면 된다. 예를 들어, (3, 2) 를 뽑는 경우 대신 17을 뽑으면 된다.

정답 코드

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

public class BOJ1941 {

    static String[] students = new String[5];
    static List<Integer> cands = new ArrayList<>();
    static int answer = 0;

    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 5; i++) {
            students[i] = bf.readLine();
        }
        comb(0, 7);
        System.out.println(answer);
    }

    static void comb(int idx, int remain) {
        if (remain == 0) {
            if (adj() && moreDasom()) {
                answer++;
            }
            return;
        }
        if (idx == 25) {
            return;
        }

        //선택하는 경우
        cands.add(idx);
        comb(idx+1 ,remain-1);
        cands.remove(cands.size()-1);

        //선택하지 않는 경우
        comb(idx+1, remain);
    }

    static boolean adj() {
        boolean[] check = new boolean[7];
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(cands.get(0));
        check[0] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 0; i < 7; i++) {
                if (check[i]) continue;
                int diff = cands.get(i) - cur;
                if (diff * diff == 1 || diff * diff == 25) {
                    if (cur % 5 == 4 && cands.get(i) % 5 == 0 || cur % 5 == 0 && cands.get(i) % 5 == 4)
                        continue;
                    q.offer(cands.get(i));
                    check[i] = true;
                }
            }
        }
        for (int i = 0; i < 7; i++)
            if (!check[i]) return false;
        return true;
    }

    static boolean moreDasom() {
        int cntDasom = 0;
        for (int cand : cands) {
            if (students[cand/5].charAt(cand%5) == 'S') {
                cntDasom++;
            }
        }
        return cntDasom > 3;
    }
}