[BOJ]1941-有名な七姫

問題の説明

なお,この問題の個数は25個に限定される.
また,隣席の隣接の意味も十字方向に広がる可能性がある.
これは一般的なBFS、DFSではできません.
また,バックトラッキングにより7つの位置を往復移動しても,クロスモデルが出現する保証はない.
始点では直線的に往復移動するだけでは既にTRUEである場所に近づくことができないからである.
だから25 C 7の組み合わせで処理しなければなりません.
そして林濤連隊を計算し、3を超えるとアウトになる.
最後に,(+)で検査を行い,隣接しているか否かを判断する.

質問リンク

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

ソースコード

package net.kang.baekjoon.gold3;

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

// https://www.acmicpc.net/problem/1941
// 조합을 모두 찾은 다음 인접, 솜의 여부를 체크하면 된다.
public class Solve1941 {
    private static char[][] seats;
    private static int[] combinations;
    private static int result;

    public static boolean checking() {
        int yeon = 0;
        for (int i = 0; i < combinations.length; i++) {
            int r = (combinations[i] - 1) / 5;
            int c = (combinations[i] - 1) % 5;
            if (seats[r][c] == 'Y') {
                yeon += 1;
            }
        }
        if (yeon > 3) {
            return false;
        } else {
            int first = combinations[0];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(first);
            Set<Integer> visited = new HashSet<>();
            visited.add(first);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                int r = (cur - 1) / 5;
                int c = (cur - 1) % 5;
                for (int i = 0; i < combinations.length; i++) {
                    if (!visited.contains(combinations[i])) {
                        int nr = (combinations[i] - 1) / 5;
                        int nc = (combinations[i] - 1) % 5;
                        // 상하 관계 (+)
                        if (Math.abs(nr - r) == 1) {
                            if (Math.abs(nc - c) == 0) {
                                queue.offer(combinations[i]);
                                visited.add(combinations[i]);
                            }
                        }
                        // 좌우 관계 (+)
                        if (Math.abs(nc - c) == 1) {
                            if (Math.abs(nr - r) == 0) {
                                queue.offer(combinations[i]);
                                visited.add(combinations[i]);
                            }
                        }
                    }
                }
            }

            return visited.size() == combinations.length;
        }
    }

    public static void recursive(int idx, int val) {
        if (idx == 7) {
            if (checking()) {
                result += 1;
            }
        } else {
            for (int i = val + 1; i <= 25; i++) {
                if (combinations[idx] == 0) {
                    combinations[idx] = i;
                    recursive(idx + 1, i);
                    combinations[idx] = 0;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        seats = new char[5][5];
        combinations = new int[7];
        result = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String row;
        for (int i = 0; i < 5; i++) {
            row = br.readLine();
            seats[i] = row.toCharArray();
        }
        for (int i = 1; i <= 25 - 6; i++) {
            combinations[0] = i;
            recursive(1, i);
            combinations[0] = 0;
        }
        System.out.println(result);
    }
}