백준 1941번: 소문난 칠공주 (JAVA)

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

1941번: 소문난 칠공주

문제

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

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

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

---

 

풀이

1. 7개의 자리를 '조합'으로 뽑기

• 이 부분을 생각하지 못하였다. '7개의 가로 및 세로로 붙어있는 경우를 뽑으려면 bfs로 하면 될 거 같은데, 모든 경우를 뽑을 수 있나? 뽑았다면, 중복한 경우는 어떻게 제외하지?'와 같은 생각이 들었다. 테트로미노 문제만 봐도, 4개의 붙어있는 원소 집합을 뽑으려고 해도 dfs만으로는 처리가 안되는데 말이다. 
• 교실의 크기가 5*5로 고정되어있는 것이 큰 힌트다: 25C7 = 480700이니, 굳이 가로, 세로가 붙어있는 쌍을 뽑는 대신, 모든 경우를 다 뽑아놓고 해당 케이스가 문제의 조건을 만족하는지 살펴봐도 된다.
  
  

2. bfs로 뽑은 7개의 자리가 연결되어있는지 확인

• 전형적인 bfs이다.
• visited처리가 조금 신경써야한다: 그냥 5*5 배열을 새로 만들어서 해도 되고, 아래 코드처럼 1차원 7개의 배열을 만들고,  (row, col) ↔ 5*row + col의 관계로 계산해도 된다. 당연히 후자가 더 빠르나, 전자로 처리해도 문제는 풀린다.

 

3. 백트래킹: 7개의 자리 조합을 만들면서 '임도연파' 학생을 이미 4명 이상 뽑았다면 그 전 단계로 돌아간다.

 

 

발상도 신선하며, 풀이에도 여러가지 테크닉을 사용하는 좋은 문제인 듯하다.

 

 

코드

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

public class Main {
    static char[][] classroom;
    static int ans;
    static boolean[] visited;
    static int[] checked = new int[7];
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        classroom = new char[5][5];
        for (int i = 0; i < 5; i++) {
            classroom[i] = br.readLine().toCharArray();
        }

        comb(0, 0, 0);
        System.out.println(ans);
    }


    static void comb(int cnt, int start, int dasomCnt) {
        if (cnt - dasomCnt > 3) return;

        if (cnt == 7) {
            visited = new boolean[7];
            bfs(checked[0]/5, checked[0]%5);
            return;
        }

        for (int i = start; i < 25; i++) {
            int row = i/5, col = i%5;
            checked[cnt] = i;
            comb(cnt+1, i+1, (classroom[row][col] == 'S')? dasomCnt+1: dasomCnt);
        }

    }


    static void bfs(int i, int j) {
        int num = 1;
        visited[0] = true;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {i, j});
        while (!queue.isEmpty()) {
            int[] rowCol = queue.poll();
            int r = rowCol[0], c = rowCol[1];
            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir], nc = c + dc[dir];
                if (nr < 0 || nr >= 5 || nc < 0 || nc >= 5) continue;
                int nxt = 5*nr + nc;
                for (int k = 0; k < 7; k++) {
                    if (!visited[k] && checked[k] == nxt) {
                        visited[k] = true;
                        num++;
                        queue.offer(new int[] {nr, nc});
                    }
                }
            }
        }
        if (num == 7) ans++;
    }
}