백준 1941 소문난 칠공주 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/1941

풀이는 다음과 같다.

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

public class Main {
    static char[][] map;
    static int answer = 0;
    static boolean[] visited;
    static int[] selected = new int[7];
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        map = new char[5][5];

        for(int r = 0 ; r < 5 ; r++) {
            map[r] = br.readLine().toCharArray();
        }

        backTracking(0, 0, 0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();

    }

    static void backTracking(int depth, int numY, int start) { //25C7 (map중에 무작위 7칸)
        if(numY >= 4) return;

        if(depth == 7) {
            visited = new boolean[7];
            BFS();
            return;
        }

        //백트래킹은 0 ~ 24지만, 배열은 5*5 2차원이다.
        //즉, 5로 나눈 몫을 행으로, 나머지를 열로 설정해주면 5*5 행렬을 표현 가능하다.
        for(int i = start ; i < 25 ; i++) {
            selected[depth] = i;
            if(map[i/5][i%5] == 'Y') {
                backTracking(depth+1, numY+1, i+1);
            }
            else {
                backTracking(depth+1, numY, i+1);
            }

        }
    }

    static void BFS() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {selected[0]/5, selected[0]%5}); //가장 처음 slected[0] 넣기
        visited[0] = true;
        int conn = 1; //몇개 연결되어있는지

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];

            for(int i = 0 ; i < 4 ; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                int ni = nr*5 + nc; //0~24의 다음 index

                if(!isValid(nr, nc)) continue;

                //내가 뽑은 7개의 index가, 서로 연결되어있는지를 검사해주는 로직.
                //selected[0]과 selected[6], 이런식으로 떨어진 숫자끼리 선택되어 연결되어 있더라도
                //아래의 for문을 통해 다 만날 수 있다.
                for(int j = 0 ; j < 7 ; j++) {
                    if(!visited[j] && selected[j] == ni) {
                        q.add(new int[] {nr, nc});
                        visited[j] = true;
                        conn++;
                    }
                }


            }
        }

        if(conn == 7) answer++;

    }

    static boolean isValid(int r, int c) { //r, c index가 유효한지
        if(r >= 0 && r < 5 && c >= 0 && c < 5) return true;
        return false;
    }



}

풀이에 대해서 설명을 하면,
5x5의 행렬은
0~24의 index, 총 25개로 표현가능하다.
index/5, index%5로
0, 0 .........4, 4 까지 모든 5x5 행렬을 나타낼 수 있다.

풀이 순서는 아래와 같다.

1. 0~24중에 무작위로 순서 없이 7개의 숫자를 백트래킹으로 뽑고 기록한다.
   기록하는 도중에, 임도연파의 학생들 (map[r][c] == 'Y') 을 세주며, 문제에서 주어진 조건대로 임도연파의 학생이 4명 이상이면 제외시켜준다.

2. 그렇게 기록된 수는 일단 7명, 그리고 임도연파의 학생이 3명 이하다를 만족한다.
   이제 해당 7명이 연속된 자리이기만 하면 된다.
   그렇게 해당 7명을 BFS로 돌려준다.
   해당 BFS에서는, 아래 로직이 핵심이다.
   내가 뽑은 학생들이 연결되어있는지를 찾아주는 로직이다.

//내가 뽑은 7개의 index가, 서로 연결되어있는지를 검사해주는 로직.
//selected[0]과 selected[6], 이런식으로 떨어진 숫자끼리 선택되어 연결되어 있더라도
//아래의 for문을 통해 다 만날 수 있다.
for(int j = 0 ; j < 7 ; j++) {
	if(!visited[j] && selected[j] == ni) {
		q.add(new int[] {nr, nc});
		visited[j] = true;
		conn++;
	}
}

큐에서 한명을 뽑고, q.poll()
해당 친구와 인접한 친구들을 구해서, int nr, int nc
그 친구들이 내가 선택한 25C7에 포함된다면 selected[j] == ni
연결되어 있다는 이야기이다. conn++

그렇게 총 7명의 친구들이 연결되어 있어야 소문난 칠공주가 결성된다.
if(conn == 7) answer++;

부족한 설명은, 풀이 내의 주석을 보고도 이해할 수 있을거라고 생각한다.