[BOJ] 1941. 소문난 칠공주

여러가지 기법이 혼합되어 있는 문제이다.

우선 전체 25개의 알파벳중 7개를 뽑는 경우의 수를 생각하였다. 백트래킹을 이용한 조합을 사용할 계획으로 7개의 알파벳을 고르는 것을 구현한 후 1차적으로 S가 4개 이상인지를 확인하였다. 그 다음 S가 4개이상임이 확인이 된다면 BFS를 이용하여 7개의 알파벳이 하나의 그룹으로 이루어져있는지 확인하였다. 만일 하나의 그룹이면 최종답을 하나추가 시켰다.

수의 범위가 구현이 가능한 범위임으로 문제에 주어진 대로 구현하는게 중요한 문제였다.

package selfStudy.chap07;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main_bj_1941_소문난칠공주  {
    
    static char[][] map;
    static int[] arr;
    static int[] result;
    static boolean[] visitForComb;
    
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int[][] mapForBFS;
    static boolean[][] visitForBFS;
    
    static Queue<Pos> queue;
    
    static class Pos{
        int i,j;
        public Pos(int i,int j) {
            this.i=i;this.j=j;
        }
    }
    
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map=new char[5][5];
        arr=new int[25];
        for(int i=0;i<25;i++)
            arr[i]=i;
        visitForComb=new boolean[25];
        result=new int[7];
    
        for(int i=0;i<5;i++) {
            String str = br.readLine();
            for(int j=0;j<5;j++)
                map[i][j]=str.charAt(j);
        }
        
        answer=0;
        comb(0,0);
        System.out.println(answer);
    }
    
    static void comb(int start,int count) {
        if(count==7) {
            if(check()) {
                if(bfs())
                    answer++;
            }
            return;
        }
        for(int i=start;i<25;i++) {
            if(visitForComb[i]==false) {
                visitForComb[i]=true;
                result[count]=arr[i];
                comb(i, count+1);
                visitForComb[i]=false;
            }
        }
    }
    
    static boolean check() {    //result에 S가 4개인지 확인
        int count=0;
        for(int i=0;i<7;i++) {
            if(map[result[i]/5][result[i]%5]=='S')
                count++;
            if(count>=4)
                return true;
        }
        return false;
    }
    
    static boolean bfs() {
        visitForBFS=new boolean[5][5];
        mapForBFS=new int[5][5];
        queue=new LinkedList<>();
        
        for(int i=0;i<7;i++) {
            mapForBFS[result[i]/5][result[i]%5]=1;
        }
        
        
        for(int i=0;i<5;i++) {
            for(int j=0;j<5;j++) {
                if(mapForBFS[i][j]==1 &&visitForBFS[i][j]==false ) {
                    queue.offer(new Pos(i, j));
                    visitForBFS[i][j]=true;
                    int count=0;
                    while(!queue.isEmpty()) {
                        Pos cur = queue.poll();
                        count++;
                        for(int dir=0;dir<4;dir++) {
                            int nextI = cur.i+di[dir];
                            int nextJ = cur.j+dj[dir];
                            
                            if(nextI<0||nextI>=5 ||nextJ<0|| nextJ>=5)
                                continue;
                            
                            if(mapForBFS[nextI][nextJ]==1 && visitForBFS[nextI][nextJ]==false) {
                                queue.offer(new Pos(nextI, nextJ));
                                visitForBFS[nextI][nextJ]=true;
                            }
                        }
                    }
                    
                    if(count==7)
                        return true;
                    else
                        return false;
                    
                }
            }
        }
        
        return false;
        
    }
}