문제

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

---

입력

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

---

출력

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

---

풀이

제한조건

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

접근방법

'조합 + 탐색'

항상 25명의 입력과 7명을 선정하면 되기에, 약 50만번으로 제한에 비해 넉넉하다.
따라서 아래와 같이 접근해본다.

1. 7명의 학생을 먼저 선정하기.
2. 7명의 학생 중, `이다솜파`가 더 많은지 확인하기.
3. 7명의 학생이 모두 인접해 있는지 확인하기.

1. 7명의 학생을 먼저 선정하기.
무작정 탐색을 하며 7명씩 선정될 때 마다 체크를 하면 중복 탐색에 대한 처리가 까다롭다.
따라서 7명을 먼저 선정해보자.

입력이 5x5이므로 총 25명의 학생이 있다. 따라서 아래와 같이 각각의 위치에 번호를 매길 수 있다.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

이제 하나씩 경우의 수를 구하고 각 경우의 수마다 다음 스텝을 진행한다.

1 2 3 4 5 6 7
1 2 3 4 5 6 8
.
.
.
19 20 21 22 23 24 25

2. 7명의 학생 중, '이다솜파'가 더 많은지 확인하기.
문제의 조건 2와 4중 어떤것을 먼저 확인해도 사실 상관은 없다.
하지만 '이다솜파'가 더 많은지 확인하는 것은 7개만 확인하면 그만이지만,

인접여부를 먼저 확인하기 위해서는 BFS를 통해 많은 작업을 거쳐야한다.
따라서 비용이 작은 작업으로 먼저 걸러내는게 시간 상 유리하다.

각 번호로 부터 x와 y의 위치를 다시 추론할 수 있으므로,
각 자리를 확인해보며, 이다솜파가 더 많은지 확인한다.

3. 7명의 학생이 모두 인접해 있는지 확인하기.
이제 인접여부를 확인해야 한다.
인접여부를 확인하기 위해 BFS를 통해 확인하는게 가장 쉽다고 생각했다.
5x5 크기의 int형 배열로 만들어주고, 선택된 7명이 존재하는 위치만 1로 표시해 줬다.

// 1 2 3 4 5 6 7이 골라졌다면,
//아래와 같이 표시
1 1 1 1 1
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

별도로 방문 처리를 해줄 무언가를 만들고 싶지 않고, 매 조합마다 다른 형태의 자리배치가 일어나므로 하나에 수정도 같이 해주자.

• 0 : 방문할 필요 없음
• 1 : 방문해야함.
• 2 : 이미 방문하였음.

//아래처럼 진행 시킨다!
2 1 1 1 1		2 2 1 1 1		2 2 2 1 1		2 2 2 2 1
1 1 0 0 0		2 1 0 0 0		2 2 0 0 0		2 2 0 0 0
0 0 0 0 0	->	0 0 0 0 0	->	0 0 0 0 0	->	0 0 0 0 0
0 0 0 0 0		0 0 0 0 0		0 0 0 0 0		0 0 0 0 0
0 0 0 0 0		0 0 0 0 0		0 0 0 0 0		0 0 0 0 0

BFS를 하면서 큐에 새로운 위치를 넣을 때마다, 카운팅을 하면,
BFS종료 시점에 7명이 모두 연결되었는지 확인가능하다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static char[][] arr;
	final static int SIZE = 5;

	static int[] select;
	static int result;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		arr = new char[SIZE][SIZE];
		for (int i = 0; i < SIZE; ++i)
			arr[i] = in.readLine().toCharArray();

		select = new int[7];
		result = 0;
		dfs(0, 0); // 순열을 먼저 구해본다. 25개 중 7개 고르기.
		System.out.println(result);
	}

	private static void dfs(int start, int depth) {
		if (depth == 7) {
			// 7개를 모두 골랐다. 조건에 맞는지 확인하자.
			if (check())
				result++;
			return;
		}

		for (int i = start; i < 25; ++i) {
			select[depth] = i;
			dfs(i + 1, depth + 1);
		}
	}

	private static boolean check() {
		int[][] checkMap = new int[5][5];
		// 조건 4.
		int count = 0;
		int x = 0;
		int y = 0;
		for (int i = 0; i < 7; ++i) {
			x = select[i] / 5;
			y = select[i] % 5;
			if (arr[x][y] == 'S')
				count++;
			checkMap[x][y] = 1;
		}

		// 조건4 불충족
		if (count < 4)
			return false;

		// 조건2 검사.
		int adjCount = 1;
		Queue<Integer> q = new ArrayDeque<>();
		q.add(select[6]);
		checkMap[x][y] = 2;
		while (!q.isEmpty()) {
			int cur = q.poll();
			x = cur / 5;
			y = cur % 5;

			for (int d = 0; d < 4; ++d) {
				int nextX = x + dx[d];
				int nextY = y + dy[d];
				if (isInRange(nextX, nextY) && checkMap[nextX][nextY] == 1) {
					adjCount++;
					checkMap[nextX][nextY] = 2;
					q.add(nextX * 5 + nextY);
				}
			}
		}

		// 조건2 불충족.
		if (adjCount != 7)
			return false;

		return true;
	}

	private static boolean isInRange(int nextX, int nextY) {
		if (0 <= nextX && nextX < SIZE && 0 <= nextY && nextY < SIZE)
			return true;
		return false;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}