[백준] 1941번 : 소문난 칠공주 - 자바(JAVA)

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

1941번: 소문난 칠공주

 

문제 해석

총 25명의 여학생들로 이루어진 여학생반은 5x5의 정사각형 격자 형태로 자리가 배치되었습니다.

이때 학생들이 S, Y 세력으로 갈라지게 되었습니다.

 

이때 세력 S파는 칠공주를 결성하고자 했습니다.

 

칠공주는 다음과 같은 규칙을 만족해야 합니다.

1. 7명으로 구성되어야 합니다.

2. 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 합니다.

3. 반드시 S세력으로 구성될 필요는 없습니다.

4. 하지만 S세력이 적어도 4명이상은 반드시 포함되어 있어야 합니다.

 

문제 풀이 전 설계

25명의 학생들로 일단 문제의 범위가 굉장히 작습니다.

따라서 완전탐색으로 접근해보고자 합니다.

 

이때 7명의 학생들을 뽑아야 하는 경우의 수는 25C7입니다.

25C7 = 480,700으로 완전탐색이 가능할 것 같습니다.

 

규칙은 굳이 순서대로 지킬 필요는 없습니다.

 

1. 25C7으로 7명을 탐색한다.

2. 이때 S세력이 4명이상이 아니라면 백트레킹

3. 서로 가로나 세로로 인전합 경우가 아니라면 백트레킹

 

코드

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

public class Main_1941_소문난칠공주 {

    static class Pos {
        int y;
        int x;

        public Pos(int y, int x) {
            this.y = y;
            this.x = x;
        }

        @Override
        public String toString() {
            return "Pos{" +
                    "y=" + y +
                    ", x=" + x +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pos pos = (Pos) o;
            return y == pos.y && x == pos.x;
        }

        @Override
        public int hashCode() {
            return Objects.hash(y, x);
        }
    }

    static char[][] board;
    static final int SIZE = 5;
    static final int GROUP_COUNT = 7;
    static int result;
    static List<Pos> students = new ArrayList<>();
    static Pos[] groupMaked = new Pos[GROUP_COUNT];
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        board = new char[SIZE][SIZE];

        String temp = null;
        for (int y = 0; y < SIZE; y++) {
            temp = br.readLine();
            for (int x = 0; x < SIZE; x++) {
                board[y][x] = temp.charAt(x);
                students.add(new Pos(y, x));
            }
        }
        //입력 끝

        //25C7
        combination(0, 0);
        System.out.println(result);
    }

    private static void combination(int start, int cnt) {
        if (cnt == GROUP_COUNT) {

            //S세력이 4명이상이 아니라서 이기지 못함
            if (!sGroupWin()) {
                return;
            }

            //그룹이 연결되어 있지 않음
            if (!groupLinked()) {
                return;
            }

            result++;
            return;
        }

        for (int i = start; i < students.size(); i++) {
            groupMaked[cnt] = students.get(i);
            combination(i + 1, cnt + 1);
        }
    }

    private static boolean sGroupWin() {
        int count = 0;
        for (Pos e : groupMaked) {
            if (board[e.y][e.x] == 'S') {
                count++;
            }
        }
        if (count >= 4) {
            return true;
        }
        return false;
    }

    private static boolean groupLinked() {
        Pos start = groupMaked[0];
        int count = 1;

        List<Pos> remainStudents = new ArrayList<>();
        for (Pos e : groupMaked) {
            remainStudents.add(e);
        }

        Queue<Pos> bfsQ = new LinkedList();
        bfsQ.add(start);
        remainStudents.remove(start);

        while (!bfsQ.isEmpty()) {
            Pos cur = bfsQ.poll();
            for (int k = 0; k < 4; k++) {
                int tempY = cur.y + dy[k];
                int tempX = cur.x + dx[k];
                if (!isValid(tempY, tempX)) {
                    continue;
                }

                Pos temp = new Pos(tempY, tempX);
                //만약에 주변에 있는친구들이 칠공주에 포함된다면?
                if (remainStudents.contains(temp)) {
                    bfsQ.add(temp);
                    remainStudents.remove(temp);
                }
            }
        }
        //연결되지 않은 학생이 남아있다면 false
        if (remainStudents.size() > 0) {
            return false;
        }

        return true;
    }

    private static boolean isValid(int tempY, int tempX) {
        return tempY >= 0 && tempX >= 0 && tempY < SIZE && tempX < SIZE;
    }
}