[백준] 1941번 : 소문난 칠공주

문제

 

 

접근 방식

일단 문제를 간단하게 정리부터 해보겠다.

1. S는 이다'솜'파이고 Y는 임도'연'파이다.
2. 5 * 5 형태로 25명의 학생이 앉아 있을 때 7명을 골라야 한다.
3. 7명의 자리는 가로나 세로로 반드시 인접해 있어야 한다. = 상하좌우 중 한 칸 인접해야 함
4. 7명 중 4명은 이다솜 파여야 한다.

2번 항목에서는 25명 중 7명을 고르는 조합을 구해야 하는 것을 알 수 있고

3번 항목에서는 고른 7명이 인접한 지 상하좌우로 탐색해야 하는 것을 알 수 있다.

 

그래서 이번 문제는 백트래킹과 BFS를 이용해서 풀 수 있기에

백트래킹으로 7명의 조합을 구하고 BFS로 이들이 인접해 있는지 확인하면 된다.

 

우선 7명의 조합을 구하는 과정은 중복 없이 구하기 위해

이미 사용한 자리는 다시 사용하지 않게 해야하고

Y(임도연파)가 등장할 때마다 재귀 호출의 매개변수로 넘겨서

4 이상인 경우에는 잘못된 조합이기 때문에 재귀 호출을 종료하게 했다.

 

위 조건들을 모두 통과하여 완성된 조합은

무조건 Y가 3명 이하고 S가 4명 이상인 조합이기 때문에

BFS를 통해 해당 조합들이 인접해 있는지 확인하여

모두 인접해 있다면 카운트를 1씩 올려주었다.

 

풀이

public class Main {

	private static int[] dx = {1, -1, 0, 0};
	private static int[] dy = {0, 0, 1, -1};
	private static char[][] seats = new char[5][5];
	private static Pair[] seven = new Pair[7];
	private static Queue<Pair> queue = new ArrayDeque<>();
	private static int count = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		combination(0, 0, 0);

		System.out.println(count);
	}

	private static void combination(int size, int start, int yeon) {
		if (yeon > 3) return;

		if (size == 7) {
			if (isLinked()) {
				count++;
			}
			return;
		}

		for (int i = start; i < 25; i++) {
			Pair pair = new Pair(i / 5, i % 5);
			seven[size] = pair;
			if (seats[pair.x][pair.y] == 'Y') {
				combination(size + 1, i + 1, yeon + 1);
			} else {
				combination(size + 1, i + 1, yeon);
			}
		}
	}

	private static boolean isLinked() {
		int[][] newSeats = new int[5][5];
		boolean[][] isVisited = new boolean[5][5];
		int s = 1;

		for (Pair pair : seven) {
			newSeats[pair.x][pair.y] = 1;
		}

		Pair pair = seven[0];
		queue.offer(pair);
		isVisited[pair.x][pair.y] = true;

		while (!queue.isEmpty()) {
			Pair cur = queue.poll();

			for (int xy = 0; xy < 4; xy++) {
				int x = cur.x + dx[xy];
				int y = cur.y + dy[xy];

				if (x < 0 || x > 4 || y < 0 || y > 4) continue;
				if (isVisited[x][y] || newSeats[x][y] == 0) continue;

				s++;
				queue.offer(new Pair(x, y));
				isVisited[x][y] = true;
			}

		}

		return s == 7;
	}

	private static class Pair {
		int x;
		int y;

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