[JAVA] 백준 (골드3) 1941번 소문난 칠공주

링크

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

---

입력 예제

YYYYY
SYSYS
YYYYY
YSYYS
YYYYY

---

출력 예제

2

---

풀이

학생을 구성하는 문제의 조건은 다음과 같다.

• 7명의 학생으로 구성되어야 한다.
• 7명의 학생이 인접해 있어야 한다.
• 이다솜파 학생이 적어도 4명 이상이어야 한다.

우선 25명의 학생 중 순서와 상관없이 7명을 뽑아야 한다. {1, 2, 3, 4, 5, 6, 7}를 뽑던, {7, 6, 5, 4, 3, 2, 1}을 뽑던 동일한 경우의 수이기 때문에 조합을 사용해야 한다.
-> $_{25}C_7$

그리고 7명을 뽑고 난 뒤,

1. 다솜파 학생이 4명이상 인지,
2. 모든 학생이 인접해 있는지를 확인하고, 답으로 카운트해야 한다.

5X5로 구성된 학생을 저장할 배열과 25명의 학생 중 선택된 학생을 저장할 배열을 생성한다.

char[][] students = new char[5][5];
boolean[] selected = new boolean[25];

7명의 학생을 뽑을 재귀 함수는 다음과 같이 구현한다. (0, 0), (0, 1), ..., (0, 4), (1, 0), ..., (4, 4)를 각각을 1차원 배열의 인덱스로 대응시켜 25명중에 7명을 순서없이 뽑는 모든 경우에 대해 독립적으로 탐색한다.

static void recur(int start, int depth, int dasomCount) {
    if (depth == 7) {
        //다솜파 학생이 4명 이상이고, 모든 학생이 인접해 있을 때 카운트
        if (dasomCount >= 4 && isAdjacent()) {
            answer++;
        }
        return;
    }
    
    //모든 경우의 수에 대해 탐색
    for (int i = start; i < 25; i++) {
        selected[i] = true;
        int r = i / 5;
        int c = i % 5;
        //다솜파 학생일 경우 카운트하여 재귀 호출
        if (students[r][c] == 'S') {
            recur(i + 1, depth + 1, dasomCount + 1);
        } else {
            recur(i + 1, depth + 1, dasomCount);
        }
        selected[i] = false;
    }
}

뽑은 학생들의 인접 여부는 BFS를 통해 확인한다. 첫번째 학생을 기준으로 탐색을 진행하며 탐색할 때마다 카운트하며 학생수만큼 카운트할 경우 true를 반환한다.

static boolean isAdjacent() {
    Queue<int[]> queue = new LinkedList<>();
    boolean[][] visited = new boolean[5][5];
    int count = 0;
    
    //첫번째로 선택된 학생 탐색
    for (int i = 0; i < 25; i++) {
        if (selected[i]) {
            queue.add(new int[]{i / 5, i % 5});
            visited[i / 5][i % 5] = true;
            break;
        }
    }
    
    //첫번째 학생의 인접 학생부터 BFS 탐색
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        count++;
        for (int i = 0; i < 4; i++) {
            int nextR = cur[0] + dr[i];
            int nextC = cur[1] + dc[i];
            if (nextR < 0 || nextR >= 5 || nextC < 0 || nextC >= 5) {
                continue;
            }
            int index = nextR * 5 + nextC;
            //인접한 학생일 경우 큐에 추가
            if (!visited[nextR][nextC] && selected[index]) {
                visited[nextR][nextC] = true;
                queue.add(new int[]{nextR, nextC});
            }
        }
    }
    return count == 7;  //인접된 학생의 수가 7일 때 true 반환
}

전체 코드

//백준
public class Main {

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static char[][] students = new char[5][5];
    static boolean[] selected = new boolean[25];
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 5; i++) {
            students[i] = br.readLine().toCharArray();
        }

        recur(0, 0, 0);

        System.out.println(answer);
    }

    static void recur(int start, int depth, int dasomCount) {
        if (depth == 7) {
            //다솜파 학생이 4명 이상이고, 모든 학생이 인접해 있을 때 카운트
            if (dasomCount >= 4 && isAdjacent()) {
                answer++;
            }
            return;
        }

        //
        for (int i = start; i < 25; i++) {
            selected[i] = true;
            int r = i / 5;
            int c = i % 5;
            //다솜파 학생일 경우 카운트하여 재귀 호출
            if (students[r][c] == 'S') {
                recur(i + 1, depth + 1, dasomCount + 1);
            } else {
                recur(i + 1, depth + 1, dasomCount);
            }
            selected[i] = false;
        }
    }

    //선택된 학생들의 인접 여부 확인
    static boolean isAdjacent() {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[5][5];
        int count = 0;

        //첫번째로 선택된 학생 탐색
        for (int i = 0; i < 25; i++) {
            if (selected[i]) {
                int r = i / 5;
                int c = i % 5;
                queue.add(new int[]{r, c});
                visited[r][c] = true;
                break;
            }
        }

        //첫번째 학생의 인접 학생부터 BFS 탐색
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            count++;

            for (int i = 0; i < 4; i++) {
                int nextR = cur[0] + dr[i];
                int nextC = cur[1] + dc[i];

                if (nextR < 0 || nextR >= 5 || nextC < 0 || nextC >= 5) {
                    continue;
                }

                int index = nextR * 5 + nextC;
                //인접한 학생일 경우 큐에 추가
                if (!visited[nextR][nextC] && selected[index]) {
                    visited[nextR][nextC] = true;
                    queue.add(new int[]{nextR, nextC});
                }
            }
        }

        return count == 7;  //인접된 학생의 수가 7일 때 true 반환
    }
}