[JAVA] BOJ 백준 1941 소문난 칠공주

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

1941번: 소문난 칠공주

💡 부분집합과 BFS를 활용하여 문제를 해결하였다.

1. 부분 집합을 통해 5X5 좌표에서 7개를 골라준다.
2. 이때 'Y'의 개수가 3개이상이면 return 해준다.
3. 7개를 골라주면 BFS를 통해 서로 연결되어 있는지 확인해준다.

전체 코드

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

public class Main {
	static char[][] classroom;
	static int result;
	static int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
    public static void main(String args[]) throws Exception{
    	BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    	classroom = new char[5][5];
    	for(int i=0; i<5; i++) {
    		String s = bf.readLine();
    		for(int j=0; j<5; j++)
    			classroom[i][j] = s.charAt(j);
    	}
    	subset(0, 0, 0, 0);
    	System.out.println(result);
    }
    static boolean[][] v = new boolean[5][5];
    static void subset(int x, int y, int yeon, int count) {
    	if(yeon >= 4 || count > 7) return;
    	boolean[][] visited = new boolean[5][5];
    	if(x==4&& y==5) {
    		ArrayDeque<int[]> q = new ArrayDeque<>();
    		f: for(int i=0; i<5; i++)
    			for(int j=0; j<5; j++)
    				if(v[i][j]) {
    					q.offer(new int[] {i, j});
    					visited[i][j] = true;
    					break f;
    				}
    		int cnt = 1;
    		while(!q.isEmpty()) {
    			int[] now = q.poll();
    			for(int d=0; d<4; d++) {
    				int nx = now[0]+dx[d];
    				int ny = now[1]+dy[d];
    				if(nx<0||ny<0||nx>=5||ny>=5|| (!v[nx][ny]) || visited[nx][ny]) continue; // v는 선택된 좌표만을 visited는 확인된 좌표인지 검사
    				cnt++;
    				visited[nx][ny] = true;
    				q.offer(new int[] {nx, ny});
    			}
    		}
    		if(cnt == 7) // 연결된것이 7개라면 7개가 서로 전부 연결되어있다는 뜻
    			result++;
    		return;
    	}
    	if(y==5) {
    		subset(x+1, 0, yeon, count);
    		return;
    	}
    	v[x][y] = true;
    	if(classroom[x][y] == 'S') // Y인 경우 yeon 증가, 아니면 그대로
    		subset(x, y+1, yeon, count+1);
    	else
    		subset(x, y+1, yeon+1, count+1);
    	v[x][y] = false;
    	subset(x, y+1, yeon, count);
    }
}