문제

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

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

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

입력
'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

출력
첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

예제 입력 1
YYYYY
SYSYS
YYYYY
YSYYS
YYYYY
예제 출력 1
2
힌트
가능한 방법은 아래와 같다.

..... .....
SYSYS SYSYS
....Y .Y...
....S .S...
..... .....

접근

행렬 크기가 5*5밖에 안 되고 그냥 7명이 인접하게 만들면 되는 거라 그냥 BFS 조지면 되겠네~ 하고 쉽게 생각했다가 내가 조져졌다ㅎㅎ...

이 문제의 핵심은 25명 중 7명을 뽑는 모든 경우의 수를 일단 조합으로 모두 구한 다음, 각각의 경우 중에서 조건을 만족시키는(1. 7명이 서로 인접해 있어야 함. 2. 이다솜파의 학생이 4명 이상이어야 함.) 조합의 개수를 세는 거였다. 전체 학생 수가 25명밖에 안 되기 때문에 이렇게 해도 상관이 없다.

그런데 나는 처음부터 무조건 7명이 인접하게 선택하려고 하다 보니 꼬이기 시작한 것 같다.
그리고 백트래킹과 BFS 둘 중 하나만 사용해야 할 것이라는 착각을 단단히 했다... 조합을 만들 때는 백트래킹을 사용하고, BFS로 인접한지 확인하면 되는 건데 백트래킹과 BFS 중 어느 하나로 그 두 가지를 모두 확인하려고 하니 하면서도 이게 맞나...? 하는 구현을 하게 됐다.

구현

1차 시도 (틀린 풀이)

import java.io.*;

class Main {
    static int result = 0;
    static boolean[][] isS = new boolean[5][5];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sCount = 0;
        for (int i = 0; i < 5; i++) {
            String input = br.readLine();
            for (int j = 0; j < 5; j++) {
                if (input.charAt(j) == 'S') {
                    sCount++;
                    isS[i][j] = true;
                    continue;
                }
                isS[i][j] = false;
            }
        }
        if (sCount < 4) {
            System.out.println(0);
            return;
        }
        backtracking(0, 0, 0, 0);
        System.out.println(result);
    }

    private static void backtracking(int row, int col, int selected, int yCnt) {
        if (Integer.bitCount(selected) == 7) {
            result++;
            return;
        }
        if (row < 0 || row >= 5 || col < 0 || col >= 5) {
            return;
        }

        int temp = 0;
        for (int i = 0; i < 4; i++) {
            if (row + dx[i] >= 0 && row + dx[i] < 5 && col + dy[i] >= 0 && col + dy[i] < 5) {
                temp |= (1 << (5 * (row + dx[i]) + col + dy[i]));
            }
        }
        if (selected == 0 || (selected & temp) > 0) {
            if (isS[row][col]) {
                backtracking((col == 4)? row + 1 : row, (col == 4)? 0 : col + 1, selected | (1 << (5 * row + col)), yCnt);
                
            } else if (yCnt < 3) {
                backtracking((col == 4)? row + 1 : row, (col == 4)? 0 : col + 1, selected | (1 << (5 * row + col)), yCnt + 1);
            }
        }
        backtracking((col == 4)? row + 1 : row, (col == 4)? 0 : col + 1, selected, yCnt);
    }
}

처음에는 비트마스킹을 약간 사용해서 인접한지 여부를 확인해보려고 했었다.
이미 선택된 학생들의 위치를 selected라는 비트에 저장하고, 새롭게 선택하려는 학생의 인접한 위치에 이미 선택된 학생들 중 어느 한 명이라도 존재하는지를 확인하는 식으로.
이렇게 하면 두 번째 학생은 첫 번째 학생과 인접하게 선택되고, 세 번째 학생은 첫 번째, 두 번째 학생과 인접하게 선택되고,,,, 이런 식으로 재귀적으로 7명의 학생이 모두 인접하게 선택될 수밖에 없을 거라고 생각했다.
그런데 챗지피티의 말로는 이렇게 하면 선택된 학생 중 어느 한 명과 인접함은 알 수 있어도 7명이 모두 인접해 있는지 여부는 알 수 없다고 한다. 솔직히 아직 이해가 잘 안 간다;;

그런데 사실 이 코드는 7공주의 조건을 만족하지 않는데 선택되는 경우뿐만 아니라, 만족을 시키는데도 선택되지 못하는 경우도 있었다. 탐색의 방향이 왼쪽 -> 오른쪽 -> 아래쪽으로 제한되어 있어서 칠공주가 다른 방향으로 앉아 있는 경우에는 발견을 하지 못했다.
예를 들어 입력이
YYYYS
YYYYY
YYYYS
YYYYY
YYSYS
인 경우, 예상 출력은 1이지만 이 코드에서는 0이 출력되었다.

정답 풀이

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

class Main {
    static int result = 0;
    static List<int[]> selected = new ArrayList<>();
    static boolean[][] isS = new boolean[5][5];
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int sCount = 0;
        for (int i = 0; i < 5; i++) {
            String input = br.readLine();
            for (int j = 0; j < 5; j++) {
                if (input.charAt(j) == 'S') {
                    sCount++;
                    isS[i][j] = true;
                    continue;
                }
                isS[i][j] = false;
            }
        }
        if (sCount < 4) {
            System.out.println(0);
            return;
        }
        makeCombination(0, 0, 0, 0);
        
        System.out.println(result);
    }

    private static void makeCombination(int row, int col, int total, int yCnt) {
        if (yCnt > 3) {
            return;
        }

        if (total == 7) {
            bfs();
            return;
        }

        for (int i = row; i < 5; i++) {
            for (int j = (i == row)? col : 0; j < 5; j++) {                
                selected.add(new int[] {i, j});
                if (isS[i][j]) {
                    makeCombination((j == 4)? i + 1 : i, (j == 4)? 0 : j + 1, total + 1, yCnt);
                } else {
                    makeCombination((j == 4)? i + 1 : i, (j == 4)? 0 : j + 1, total + 1, yCnt + 1);
                }
                selected.remove(selected.size() - 1);
            }
        }
    }

    private static void bfs() {
        boolean[] isValid = new boolean[7];
        int count = 1;
        Queue<int[]> q = new LinkedList<>();
        q.offer(selected.get(0));
        isValid[0] = true;

        while (!q.isEmpty() && count < 7) {
            int[] curr = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextRow = curr[0] + dx[i];
                int nextCol = curr[1] + dy[i];
                if (nextRow >= 0 && nextRow < 5 && nextCol >= 0 && nextCol < 5) {
                    for (int k = 0; k < 7; k++) {
                        if (selected.get(k)[0] == nextRow && selected.get(k)[1] == nextCol && !isValid[k]) {
                            count++;
                            isValid[k] = true;
                            q.offer(selected.get(k));
                        }
                    }
                }
            }
        }
        if (count == 7) {
            result++;
        }
    }
}

다른 분들의 풀이를 조금 참고해서, 일단 백트래킹으로 가능한 모든 조합을 찾은 다음, 7명의 선택이 완료되면 그때 BFS로 연결 여부를 확인하는 식으로 구현을 수정했다.