[Gold III] 소문난 칠공주 - 1941 (Java)

문제 요약

총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.
여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

---

문제 분석

1. 지도의 각 위치들(pointArr), 총 25곳의 위치들에서 7개의 조합을 뽑는다.
2. 각 조합 안에 S가 4개 이상이 있는지 파악한다.
3. 7개의 위치가 서로 가로나 세로로 인접해 있는지 판단.

---

코드

package Week24;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_1941 {
    static char[][] map = new char[5][5];
    static int[][] pointArr = new int[25][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        int point = 0;
        // map에 값 추가
        for (int r = 0; r < 5; r++) {
            input = br.readLine();
            for (int c = 0; c < 5; c++) {
                map[r][c] = input.charAt(c);
                pointArr[point++] = new int[]{r, c};
            }
        }
        /*
            문제조건
            1. 7명의 구성
            2. 7명은 서로 가로나 세로로 인접
            3. S가 4개 이상
            문제풀이
            1. 지도의 각 위치들(pointArr), 총 25곳의 위치들에서 7개의 조합을 뽑는다.
            2. 각 조합 안에 S가 4개 이상이 있는지 파악한다.
            3. 7개의 위치가 서로 가로나 세로로 인접해 있는지 판단.
         */
        System.out.println(combination(0, 0, new int[7], new boolean[25]));
    }

    private static int combination(int start, int depth, int[] selected, boolean[] booleans) {
        if (depth == 7) {
            // S 개수 확인
            int sCnt = 0;
            for (int i = 0; i < 7; i++) {
                int r = pointArr[selected[i]][0];
                int c = pointArr[selected[i]][1];
                sCnt += map[r][c] == 'S' ? 1 : 0;
            }
            if (sCnt < 4) return 0;

            // 서로 가로세로로 이웃하는지 확인
            boolean isAdjacent = bfs(selected);
            if (isAdjacent) {
                return 1;
            } else {
                return 0;
            }
        }
        int count = 0;
        for (int i = start; i < 25; i++) {
            if (!booleans[i]) {
                booleans[i] = true;
                selected[depth] = i;
                count += combination(i + 1, depth + 1, selected, booleans);
                booleans[i] = false;
            }
        }
        return count;
    }

    private static boolean bfs(int[] selected) {
        Queue<int[]> q = new LinkedList<>();
        boolean[] visited = new boolean[7]; // 선택된 7명에 대한 방문 여부
        int count = 0; // 방문한 학생 수

        // 첫번째 학생을 시작점으로 설정
        q.add(pointArr[selected[0]]);
        visited[0] = true;
        count++;

        while (!q.isEmpty()) {
            int[] curr = q.poll();

            // 인접한 학생을 찾아서 큐에 추가
            for (int i = 0; i < 7; i++) {
                if (!visited[i]) {
                    int[] next = pointArr[selected[i]];
                    // 현재의 위치(curr)와 다음의 위치(next)가 인접한지 확인
                    // x 좌표 또는 y 좌표의 차이가 정확히 1인지 확인
                    if (Math.abs(curr[0] - next[0]) + Math.abs(curr[1] - next[1]) == 1) {
                        q.add(next);
                        visited[i] = true;
                        count++;
                    }
                }
            }
        }
        return count == 7;
    }
}

---

정리

개선할 점

비트마스킹을 사용하여 위치선택, 조합 과정에서 S를 기준으로 백트래킹하

---