[알고리즘] Java / 백준 / 소문난 칠공주 / 1941

[알고리즘] Java / 백준 / 소문난 칠공주 / 1941

문제

문제 링크

접근 방식

1. 재귀로 Combination을 구현하고 0 ~ 24 중 7개의 수를 선택한다.
2. 선택한 7개의 수를 좌표로 변환하고 S파가 4명 이상인지 확인한다.
3. 2번을 만족할 때 7개의 좌표 중 한 좌표에서 bfs 탐색했을 때 7개의 좌표가 모두 탐색된다면 경우의 수를 1 높인다.

수를 좌표로 변환하기

ex )

17 → (3,2)

세로 r : 17/5 = 3

가로 c : 17%5 = 2

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main_1941 {

	// 25 C 7 구하기
	// 구한 7개의 학생중 4명 이상이 S파인지 확인
	// 구한 7개의 학생이 인접해있는지 확인
	
	static char[][] mat;
	static int[] numList;
	static int answer;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		mat = new char[5][5];
		
		for(int i=0;i<5;i++) {
			String line = br.readLine();
			for(int j=0;j<5;j++) {
				mat[i][j] = line.charAt(j);
			}
		}
		
		numList = new int[7];
		answer = 0;
		
		combi(0,7,0);
		
		System.out.println(answer);
	}
	
	static boolean[][] visited;
	public static void combi(int start, int target, int cnt) {
		if(cnt == target) {
			// 구한 7명의 학생 중 4명 이상이 S파인지 확인
			if(!isSGroup()) return;
			
			// 구한 7명의 학생이 인접해있는지 확인
			int v = 0; // v가 2 이상이면 인접하지 않은 것
			visited = new boolean[5][5];
			for(int i=0;i<7;i++) {
				int r = numList[i]/5;
				int c = numList[i]%5;
				if(!visited[r][c]) {
					if(v == 1) return;
					v++;
					bfs(r,c);
				}
			}
			answer++;
			return;
		}
		
		for(int i=start;i<25;i++) {
			numList[cnt] = i;
			combi(i+1,target,cnt+1);
		}
		
	}
	
	public static boolean isSGroup() {
		int cnt = 0;
		for(int i=0;i<7;i++) {
			int r = numList[i]/5;
			int c = numList[i]%5;
			if(mat[r][c] == 'S')
				cnt++;
		}
		
		if(cnt>=4) return true;
		
		return false;
	}
	
	public static class Node{
		int r;
		int c;
		int cnt;
		
		Node(int r, int c, int cnt){
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
	}
	
	static int dr[] = {0,1,0,-1};
	static int dc[] = {1,0,-1,0};
	public static void bfs(int r, int c) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(r,c,1));
		
		visited[r][c] = true;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			if(node.cnt == 7) continue;
			
			for(int i=0;i<4;i++) {
				int nr = node.r + dr[i];
				int nc = node.c + dc[i];
				
				if(nr<0||nr>=5||nc<0||nc>=5||visited[nr][nc]) continue;
				boolean canMove = false;
				for(int j=0;j<7;j++) {
					if(numList[j] == nr*5+nc) {
						canMove = true;
						break;
					}
				}
				
				if(canMove) {
					visited[nr][nc] = true;
					q.add(new Node(nr,nc,node.cnt+1));					
				}
			}
		}
	}

}