백준 1941 소문난 칠공주

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

소문난 칠공주!

처음에는 dfs 백트래킹 을 이용해서

십자가 배치를 일일히 다 해주려고했다..

25C7 했는데.. 스택이 40만개가량.. 당연히 오버플로우 펑!
터질꺼라는걸알았는데..

백트래킹을 써서

4개부터 현재 S의 갯수 의 최소조건 1명이 안되면 return 되는식으로?? 생각했는데..그래도 펑터져버렸다 ㅎㅎ

그래서 보니까 dfs로 일일히 배치가아닌 조합으로 뽑아와야된다..

좌표로 전체로 x,y값 배치로 꺼내와도되고 25개 임의수 배열해서 집어넣어도된다..

5 * 5 일 배열 기준으로 1~10까지임의으수를 배치한다고 예를들면

변경된 좌표를 좀더 식을 세워서 첫줄만 보면

이게 핵심인거같다..

메인 로직

1. 0~24까지 조합 7개 구하기 + 선택했으면 배열에 넣어주면서 진행
2. 고른값을 먼저 1차적으로 이다솜파 4명이상인지 검사
3. 검사에 통과했다면 연결검사
   3.1 연결검사에는 스택사용하면 당연히 펑 터지므로 bfs로 queue로 해준다!

import java.util.*;
import java.io.*;
public class 소문난칠공주 {
	static class  Person{
		int x;
		int y;
		public Person(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
	}

	static int N;
	static int answer;
	static int[][] array;
	static int[] member;
	static boolean[][] use;
	static int[] dx = new int[] {0,1,-1,0};
	static int[] dy = new int[] {1,0,0,-1};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = 7;
		answer=0;
		array = new int[5][5];
		use = new boolean[5][5];
		member = new int[7];
		for(int i=0;i<5;i++) {
			String line  = br.readLine();
			for(int j=0;j<5;j++) {
				if(line.charAt(j)=='Y') {
					array[i][j] = 0;
				}
				else {
					array[i][j] = 1;
				}
			}
		}
		pri(0,0);
		System.out.println(answer);
	}
	
	
	static public void pri(int count, int cur) {
		if(count==7) {
			if(scount()) {
				if(connect()) answer++;
			}
			return;
		}

		
		for(int i=cur;i<25;i++) {
			member[count]=i;
			use[i/5][i%5] =true;
			pri(count+1,i+1);
			use[i/5][i%5] = false;
		}
	}
	
	
	static public boolean connect() {
		
		boolean visited[][] = new boolean[5][5];
		int firstx=-1;
		int firsty = -1;
		Loop:
		for(int i=0;i<5;i++) { 
			for(int j=0;j<5;j++) { //시작점찾기
				if(use[i][j]) { //사용중이라면 
					firstx=i;
					firsty=j;
					break Loop;
				}
			}
		}
		
		visited[firstx][firsty]=true;
		Queue<Person> q = new LinkedList<>();
		q.add(new Person(firstx,firsty));
		int count=0;
		while(!q.isEmpty()) {
			Person cur = q.poll();
			count++;
			
			if(count==7) break;
			for(int j=0;j<4;j++) {
				int nx = cur.x+dx[j];
				int ny = cur.y+dy[j];
				
				if(nx<0 || nx >4 || ny <0 || ny>4) continue;
				if(use[nx][ny] && !visited[nx][ny]) {
					visited[nx][ny]=true;
					q.add(new Person(nx,ny));
				}
			}
			
		}
		if(count==7) return true;
		return false;
	}
	static public boolean scount() {
		int count = 0;
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				if(use[i][j]) { //사용중이라면 
					count+= array[i][j];
				}
			}
		}
		if(count<4) return false;
		return true;
	}
	
}

조합식을 변수를 잘못설정해서..많은시행착오가있었다..

골드3~4문제 한번 다시풀고 2나 1을 풀고 백트래킹도 넘어가자!