[백준] 소문난 칠공주 1941번 (java) 조합

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

 

풀이 방법

해당 문제를 보고 완전 탐색 문제인 것을 확인했다. 

처음엔 단순히 dfs, bfs를 통해 임도연 파가 3명이 넘어가면 중단하며 인접한 7명의 사람을 선택하는 방법으로 풀이할까 했지만, 이렇게 한다면 아래 이미지와 같은 케이스는 탐색하지 못한다. 

그렇기 때문에 각 위치의 인덱스를 이용해서 7명을 뽑고, 7명 중 임도연파 수를 세고, 인접한 지 검사하는 방법으로 완전탐색을 수행해야 한다.

인덱스는 0부터 24까지 두었고 y좌표를 인덱스 / 5, x좌표를 인덱스 % 5로 설정해서 y, x좌표를 구했다.

여기서 visited배열은 선택된 사람 adjVisited는 인접 검사를 진행하기 위한 bfs 수행 시 방문 여부이다.

 

7명 구하는 dfs 함수

public static void dfs(int idx, int cnt) {
        if (board[idx / 5].charAt(idx % 5) == 'Y') { // 임도연파이면 카운트 증가
            yCnt++;
        }
        visited[idx] = 1;
        if (yCnt >= 4) { //4명 이상이면 리턴
            yCnt--;
            visited[idx] = 0;
            return ;
        }
        if (cnt == 7) { //7명 모았으면 인접한지 검사
            if (Adjacency()) ans++;
        }
        for (int i = idx + 1;i < 25;i++) { // 다음 조합 탐색
            dfs(i, cnt + 1);
        }
        visited[idx] = 0;  // 백트레킹
        if (board[idx / 5].charAt(idx % 5) == 'Y') {
            yCnt--;
        }
    }

 

인접한 지 탐색할 때 하나의 visited 된 사람만 큐에 넣고 해당 사람에서 bfs를 돌며 끝났을 때 cnt의 값이 7이 되는지 검사를 진행했다.

7이 된다면 모두 인접, 미만이라면 한 명이라도 떨어진 사람이 존재한다.

전체 코드

import java.io.*;
import java.util.*;


public class P_1941 {

    static String[] board = new String[5];
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int ans = 0;
    static int[] visited = new int[25], adjVisited = new int[25];

    static class Node {
        int y;
        int x;

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

    public static boolean Adjacency() {
        Queue<Node> q = new LinkedList<>();
        Arrays.fill(adjVisited, 0);
        for (int i = 0;i < 25;i++) {
            if (visited[i] == 1) {
                q.add(new Node(i / 5, i % 5));
                adjVisited[i] = 1;
                break;
            }
        }
        int cnt = 1;
        while (!q.isEmpty()) {
            Node cur = q.poll();
            for (int i = 0;i < 4;i++) {
                int ny = cur.y + dy[i];
                int nx = cur.x + dx[i];
                if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5) continue;
                if (visited[ny * 5 + nx] == 1) {
                    if (adjVisited[ny * 5 + nx] == 0) {
                        adjVisited[ny * 5 + nx] = 1;
                        q.add(new Node(ny, nx));
                        cnt++;
                        if (cnt == 7) return true;
                    }
                }
            }
        }
        return false;

    }
    static int yCnt = 0;
    public static void dfs(int idx, int cnt) {
        if (board[idx / 5].charAt(idx % 5) == 'Y') {
            yCnt++;
        }
        visited[idx] = 1;
        if (yCnt >= 4) { //4 개 이상이면 리턴
            yCnt--;
            visited[idx] = 0;
            return ;
        }
        if (cnt == 7) {
            if (Adjacency()) ans++;
        }
        for (int i = idx + 1;i < 25;i++) {
            dfs(i, cnt + 1);
        }
        visited[idx] = 0;
        if (board[idx / 5].charAt(idx % 5) == 'Y') {
            yCnt--;
        }
    }
    //체크하고 백트레킹 하고 체크하고 백트레킹하고
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0;i < 5;i++) {
            board[i] = br.readLine();
        }
        for (int i = 0;i < 25;i++) {
            dfs(i, 1);
        }
        System.out.println(ans);

    }
}