[BOJ] 1941. 소문난 칠공주 - JAVA

🔗 문제

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

1941번: 소문난 칠공주

 

💻 풀이 및 코드

문제 유형 : 조합, 벡트랙킹,  BFS

 

YYYYY
SYSYS
YYYYY
YSYYS
YYYYY

총 25명 중 가로세로가 인접한 7명을 구하는데, 그 중 솜파(S)가 4명 이상으로 구성된 조합의 갯수

 

풀이

• 그래프로 표시된 Y 와 S 에 차례대로 0~24 번이 번호를 부여한다.
• 총 25명 중 7명을 뽑는 조합을 구한다.
• 7명이 넘어가거나, 솜파가 4명이 이하라면 return 한다. (백트랙킹)
• 조합 중 BFS 를 통해 인접했는지 체크한다.

느낀점

처음엔 DFS 로 탐색하면서 조건에 맞는지 확인했다. (7명, S 가 4명 이상) 근데 틀렸다. 뭐가 문제였을까..

 

전체 코드

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

/*
 * 1~25번 번호를 부여
 * 25명 중 7명을 뽑는 조합을 구함
 * 솜파가 4명이 이상이고 인접했는지 체크해서 맞다면 ans++
 */
public class Main_bj_1941_소문난칠공주_sol2 {
	
	static char[][] graph;
	static int ans = 0;
	static int[] selected;
	static boolean[] isSelected;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_1941.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		graph = new char[5][5];
		
		for(int i=0; i<5; i++) {
			String s = br.readLine();
			for(int j=0; j<5; j++) {
				graph[i][j]  = s.charAt(j);
			}
		}
		
		selected = new int[7];
		isSelected = new boolean[25];
		find(0, 0, 0);
		System.out.println(ans);
		br.close();
	}
	
	// 25명 중에 7명을 고르는 조합
	static void find(int idx, int dasom, int start) {
		if(idx > 7) return;
		if(idx == 7 && dasom < 4) return;
		
		if(idx == 7) {
			// 7명이 인접했는지 체크
			if(checkAdj()) {
				ans++;
			}
			
			return;
		}
		
		for(int i=start; i<25; i++) {
			selected[idx] = i;
			isSelected[i] = true; 
			if(graph[i/5][i%5] == 'S') {
				find(idx+1, dasom+1, i+1);
			} else {
				find(idx+1, dasom, i+1);
			}
			isSelected[i] = false;
		}
		
		
	}
	
	static int[] du = {-1, 0, 1, 0};
	static int[] dv = {0, 1, 0, -1};
	
	static boolean checkAdj() {
		boolean[][] visited = new boolean[5][5];
		int number = selected[0];
		visited[number/5][number%5] = true;
		Queue<Integer> que = new ArrayDeque<>();
		que.add(selected[0]);
		
		int cnt = 1;
		while(!que.isEmpty()) {
			int now = que.poll();
			
			for(int d=0; d<4; d++) {
				int nu = now/5 + du[d];
				int nv = now%5 + dv[d];
				
				if(nu<0 || nu>=5 || nv<0 || nv>=5 || visited[nu][nv]) continue;
				if(!isSelected[nu*5+nv]) continue;
				visited[nu][nv] = true;
				cnt++;
				que.add(nu*5+nv);
			}
		}
		
		if(cnt==7) return true;
		else return false;
	}

}

 

DFS 로 풀었다가 틀린 코드

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

public class Main_bj_1941_소문난칠공주 {
	
	static char[][] graph;
	static int ans = 0;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_1941.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		graph = new char[5][5];
		for(int i=0; i<5; i++) {
			String s = br.readLine();
			for(int j=0; j<5; j++) {
				graph[i][j] = s.charAt(j);
			}
		}
		
		for(int i=0; i<5; i++) {
			for(int j=0; j<5; j++) {
				boolean[][] visited = new boolean[5][5];
				visited[i][j] = true;
				if(graph[i][j] == 'S') {
					dfs(1, 1, i, j, visited);
				} else {
					dfs(1, 0, i, j, visited);
				}
			}
		}
		
		System.out.println(ans);
		br.close();
	}
	
	static int[] du = {-1, 0, 1, 0};
	static int[] dv = {0, 1, 0, -1};
	
	static void dfs(int total, int dasom, int u, int v, boolean[][] visited) {
		if(total > 7) return;
		if(total==7 && dasom < 4) return;
		
		if(total == 7) {
			ans++;
			
			for(int i=0; i<5; i++) {
				for(int j=0; j<5; j++) {
					if(visited[i][j]) {
						System.out.print(graph[i][j]);
					} else {
						System.out.print(".");
					}
				}
				System.out.println();
			}
			System.out.println();
			
			return;
		}
		
		int nu=0, nv=0;
		for(int d=0; d<4; d++) {
			nu = u + du[d];
			nv = v + dv[d];
			
			if(nu<0 || nu>=5 || nv<0 || nv>=5 || visited[nu][nv]) continue;
			visited[nu][nv] = true;
			if(graph[nu][nv] == 'S') {
				dfs(total+1, dasom+1, nu, nv, visited);
			} else {
				dfs(total+1, dasom, nu, nv, visited);
			}
			visited[nu][nv] = false;
		}
	}
	

}

---

Reference

https://data-make.tistory.com/476

[BOJ] 1941. 소문난 칠공주(조합, DFS, BFS).java