[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);
    }
}