[백준] 1941 소문난 칠공주

1. 문제

 

2. 접근방법

처음엔 DFS로 풀어보려 했지만 DFS로는 찾기 힘든 모양들이 있다.

이 예제에서의 이런 T자 모양 이라던가 十 자 라던가

어떻게든 DFS로 풀어보고자 이 방법 저 방법 다 해봤지만 예외처리 할 부분이 너무 많아서 결국 포기했다.

 

다른 방법으로는 어차피 주어지는 입력이 5*5 고정이니 그냥 25개 중 7개를 뽑아 모든 경우의 수를 찾고 인접했는지 이다솜파가 4명이상 포함 되었는지 검사해주는 조합으로 풀 수 있다.

 

모든 경우의 수라고 해봤자 25 C 7 이면 480,700개 뿐이라 시간제한에도 안전하다.

 

즉 25개 중 7개를 뽑는 조합을 모조리 구하고 조건에 맞는 것만 걸러내면 된다.

3. 풀이

조건을 정리하면 아래 2가지 이다.

1. 모든 칠공주가 인접해 있는가?

2. 칠공주 안에 이다솜파가 4명 이상인가?(임도연파가 3명 이하인가?)

 

조합을 뽑을때 각 자리마다 번호를 매겨준 상태로 뽑고

0   1   2  3   4

5   6   7  8   9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

 

각 위치의 row,col 값은 (위치 / 5) , (위치 % 5) 로 구할 수 있다.

인접해 있는지 조건 검사를 할때는

각 숫자에 위아래는 -5 +5 왼쪽 오른쪽은 -1 +1을 하여 쉽게 검사 할 수 있다.

 

풀이

1. 맵 입력받기

2. 0~24 중 7개 뽑는 조합 만들기

3. 조합을 만드는 도중 뽑은 Y가 3개 초과가 되면 return

4. 뽑힌 조합이 인접해 있는지 검사 이상 없다면 result++

5. result 출력

 

4. 자바코드

package 백준;

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

public class P1941소문난칠공주 {
	static char map[][] = new char[5][5];
	static int result;
	static int sel[] = new int [7];
	static void comb(int idx ,int selidx,int Y) {
		if(Y>3)
			return;
		if(selidx == 7) {
			if(check()) {
				result++;
			}
			return;
		}
		if(idx == 25)
			return;
		
		sel[selidx] = idx;
		int isY = map[idx/5][idx%5] == 'Y'? 1 : 0;
		comb(idx+1,selidx+1,Y+isY);
		comb(idx+1,selidx,Y);
			
		
	}
	static boolean check() {
		//뭐든 요소가 연결되어있는지 확인
		boolean [] visit = new boolean [7];
		visit[0] =true;
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(0);
		int cnt = 1;
		while(!que.isEmpty()) {
			int i = que.poll();
			for(int j = 0 ; j < 7 ; j++) {
				if(i==j || visit[j])
					continue;
				if(sel[i] % 5 == 0) // 가장 왼쪽 벽일때
					if(sel[i] - 1 == sel[j])
						continue;
				if(sel[i] % 5 == 4) //가장 오른쪽 벽일때
					if(sel[i] + 1 == sel[j])
						continue;
				if(sel[i] - 1 == sel[j] || sel[i] + 1 == sel[j] || sel[i]+5 == sel[j] || sel[i] - 5 == sel[j]) {
					que.offer(j);
					visit[j] = true;
					cnt++;
				}
			}
		}
		if(cnt != 7) //연결이 하나라도 안되어있으면
			return false;
		
		return true; 
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 5; i++) {
			String line = br.readLine();
			for (int j = 0; j < 5; j++) {
				map[i][j] = line.charAt(j);
			}
		}
		comb(0,0,0);
		System.out.println(result);
		
	}
}

5. 마치며

이 문제는 처음에 DFS로는 별 고민 안하고 어 25개 중에 7개만 뽑으면 그냥 조합가지고 해도 되겠는데? 싶어서 바로 조합으로 풀었다. 그러곤 혼자서 이야 아무도 조합으로는 안풀었겠지 하면서 다른 사람것들 찾아봤는데 다들 조합으로 풀었다드라.. 

 

나중에서야 이게 DFS로 안풀리나? 싶어서 이것 저것 다 해봤는데 결국 포기 ,, 그냥 조합이 정답이었나 보다.

 

 

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

1941번: 소문난 칠공주