[BaekJoon] 1941 소문난 칠공주 (Java)

1.  문제 링크

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

2.  문제

요약

• 총 25명의 여학생들로 이루어진 여학생반은 5 x 5의 정사각형 격자 형태로 자리가 배치되어 있습니다.
• 모든 여학생이 '이다솜파'와 '임도연파'의 두 파로 갈라지게 되었고, '임도연파'가 세력을 확장시켜 '이다솜파'의 학생들은 '소문난 칠공주'를 결성하려고 합니다.
• '소문난 칠공주'는 다음과 같은 규칙을 만족해야 합니다.
  1. 7명의 여학생들로 구성되어야 합니다.
  2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 합니다.
  3. 화합과 번영을 위해, 반드시 '이다솜파'의 학생들로만 구성될 필요는 없습니다.
  4. 생존을 위해, '이다솜파'가 반드시 우위를 점해야 합니다. 따라서 7명의 학생 중 '이다솜파'의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 합니다.
• 여학생반의 자리 배치도가 주어졌을 때, '소문난 칠공주'를 결성할 수 있는 모든 경우의 수를 구하는 문제입니다.
• 입력: 'S'('이다솜파'의 학생) 또는 'Y'('임도연파'의 학생)를 값으로 갖는 5 * 5 행렬이 첫 번째 줄부터 5개의 줄에 걸쳐 주어집니다.
• 출력: 첫 번째 줄에 '소문난 칠공주'를 결성할 수 있는 모든 경우의 수를 출력합니다.

3.  소스코드

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

public class Main {
    static final int SIZE = 5, LAST = 7, SOM = 4;
    static int answer;
    static char[][] map;
    static int[] eachX, eachY, dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
    static void input() {
        Reader scanner = new Reader();
        map = new char[SIZE][SIZE];
        for(int row = 0; row < SIZE; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < SIZE; col++) map[row][col] = info.charAt(col);
        }
    }

    static void solution() {
        answer = 0;
        eachX = new int[SIZE * SIZE];
        eachY = new int[SIZE * SIZE];
        for(int idx = 0; idx < SIZE * SIZE; idx++) {
            eachX[idx] = idx / SIZE;
            eachY[idx] = idx % SIZE;
        }
        chooseStudents(0, 0, new int[LAST]);
        System.out.println(answer);
    }

    static void chooseStudents(int num, int idx, int[] students) {
        if(num == LAST) {
            bfs(students);
            return;
        }
        if(idx == SIZE * SIZE) return;
        students[num] = idx;
        chooseStudents(num + 1, idx + 1, students);
        chooseStudents(num, idx + 1, students);
    }

    static void bfs(int[] students) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[LAST];
        visited[0] = true;
        queue.offer(students[0]);
        int equalCnt = 1, som = 0;
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            if(map[eachX[cur]][eachY[cur]] == 'S') som++;
            for(int dir = 0; dir < 4; dir++) {
                for(int next = 1; next < LAST; next++) {
                    int cx = eachX[cur] + dx[dir], cy = eachY[cur] + dy[dir];
                    if(!visited[next]) {
                        if(cx == eachX[students[next]] && cy == eachY[students[next]]) {
                            visited[next] = true;
                            queue.offer(students[next]);
                            equalCnt++;
                        }
                    }
                }
            }
        }
        if(equalCnt == LAST && som >= SOM)
            answer++;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

4.  접근

• 여학생반의 자리 배치도를 map이라는 2차원 배열에 저장하고 1차원 배열 eachX, eachY를 생성하여 값을 넣습니다.
  • 이후에 각 학생들을 0부터 24로 나타낼 것인데, 이 때 각 학생이 어디에 위치해있는지를 나타내기 위해 eachX에 해당 학생의 행의 값, eachY에 해당 학생의 열의 값을 담습니다.
  • 0번 학생은 (0, 0), 1번 학생은 (0, 1), ..., 4번 학생은 (0, 4), 5번 학생은 (1, 0), ... 이런 식으로 학생들을 배치시킵니다.
  • 그렇기 때문에 eachX에는 (학생 번호) / 5를 구해서 넣고, eachY에는 (학생 번호) % 5를 구해서 넣습니다.
• 0부터 24까지의 학생들 중 7명을 고르는 모든 경우의 수를 만들어보고 각 경우가 인접해있는지, '이다솜파'의 학생이 4명 이상인지 확인하여 가능한 모든 경우의 수를 구합니다.
  • 0번 학생부터 24번 학생까지 모든 학생들을 돌면서 해당 학생을 '소문난 칠공주'에 넣는 경우와 넣지 않는 경우를 살핍니다.
  • '소문난 칠공주'에 들어간 학생이 7명이 됐다면 BFS를 통해 인접해있는지, '이다솜파'의 학생이 4명 이상인지 확인합니다.
    • Queue에 첫 번째 학생을 넣고 방문 체크를 위해 visited 배열을 생성합니다.
      • '이다솜파'의 학생의 수를 나타내는 som이라는 변수를 생성하여 값을 0으로 초기화하고 인접해있는 학생들의 수를 나타내는 equalCnt라는 변수를 생성하고 값을 1로 초기화합니다.
      • Queue가 비워질 때까지 Queue에서 값을 뽑아 해당 위치의 학생이 '이다솜파'의 학생이라면 som의 값을 1 증가시켜줍니다.
      • 또한, 해당 위치의 상하좌우 위치를 보고 '소문난 칠공주'에 넣은 학생들이 그 위치들에 포함되어있는지 확인합니다.
      • 만약 인접해있는 위치에 있는 학생이 있고 그 학생을 아직 방문하지 않았다면 방문 체크를 해주고 Queue에 해당 위치의 학생을 넣어준 후에 equalCnt를 1 증가시킵니다.
      • Queue가 비워질 때까지 탐색한 후에 equalCnt가 7이고 som이 4 이상이라면 해당 경우는 가능한 경우이므로 가능한 경우의 수를 1 증가시켜줍니다.