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

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

1941번: 소문난 칠공주

해당 문제는 일반적인 BFS문제랑 문제 접근이 달라서 아이디어를 생각하기 힘들었습니다.

먼저 조합을 통해 학생들을 7명을 뽑습니다. 그 중 S가 4이상인지 확인하고 DFS를 통해서 각각의 뽑은 친구들이 연결되어 있는지 확인하였습니다. 

저는 다음과 같이 1차원 배열로 해당 학생의 위치를 저장하였습니다.

(0,0) -> 0 = 0

(1,1) -> 1*5 + 1 = 6

친구들이 연결되어있는지는 아무 학생을 Queue에 넣고 그 학생부터 BFS를 통해 각각의 학생들이 인접한지 확인하였습니다.

package BOJ.DFS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1941 {
    static final int SIZE = 5;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[][] map = new char[SIZE][SIZE];
        for(int i = 0 ; i < SIZE ; i++){
            String command = br.readLine();
            for(int j = 0 ; j < SIZE ; j++){
                map[i][j] = command.charAt(j);
            }
        }
        int result  = cal(map);
        System.out.println(result);
    }
    static final int dy[] = {-1,0,1,0};
    static final int dx[] = {0,1,0,-1};
    private static int cal(char[][] map){
        int result = 0;
        int[] choice = new int[7];
        result = comb(0,choice,0,map);
        return result;
    }
    private static int comb(int depth, int[] choice, int start,char[][] map){ // 7명 뽑기
        if(depth == 7){
//            System.out.println(Arrays.toString(choice));
            if(checkCountS(choice,map) && checkNear(choice)){
                return 1;
            }
            return 0;
        }
        int result = 0;
        for(int i = start ; i < SIZE * SIZE ; i++){
            choice[depth] = i;
            result += comb(depth+1, choice,i + 1,map);
        }
        return result;
    }
    private static boolean checkCountS(int[] choice, char[][]map){
        int count = 0;
        for(int num : choice){
            int y = num / SIZE;
            int x = num % SIZE;
            if(map[y][x] == 'S'){
                count++;
            }
        }
        if(count >= 4){
            return true;
        }
        return false;
    }
    private static boolean checkNear(int[] choice) { // 인접한지 확인
        boolean[][] visited = new boolean[SIZE][SIZE];
        boolean[][] needVisited = new boolean[SIZE][SIZE];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0 ; i < 7 ; i++){
            int y = choice[i] / SIZE;
            int x = choice[i] % SIZE;
            if(i == 0){
                queue.offer(new int[] {y,x});
                visited[y][x] = true;
            }
            needVisited[y][x] = true;
        }
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            for(int i = 0; i < 4; i++){
                int ny = now[0] + dy[i];
                int nx = now[1] + dx[i];
                if(ny >= 0 && ny < SIZE && nx >= 0 && nx < SIZE && needVisited[ny][nx] && !visited[ny][nx]){
                    visited[ny][nx] = true;
                    queue.offer(new int[] {ny,nx});
                }
            }
        }
        for(int num : choice){
            int y = num / SIZE;
            int x = num % SIZE;
            if(visited[y][x] != needVisited[y][x]){
                return false;
            }
        }
        return true;
    }
}