[백준] 1941 소문난 칠공주 (Java)

[1941 소문난 칠공주]

난이도: 골드3

1941번: 소문난 칠공주

문제

입력

출력

---

[아이디어]

BFS와 백트래킹 그리고 조합을 사용하는 문제이다.

단순한 BFS를 사용하면 십자가모양을 만들어낼 수 없기 때문에 조합을 사용하여 먼저 7명을 선택해준다.

이 때, 5 x 5 로 학생들이 주어지기 때문에 0 ~ 24로 번호를 정하고 조합을 구하면 편하다.

n번 학생의 (행, 열)을 구하는 방법은 (n / 5, n % 5) 이므로 번호를 좌표로 변환하는 것은 크게 어렵지 않다.

7명을 모두 선택한 후에는 그 안에 '이다솜'파가 몇 명인지 먼저 세어보고 4명 이상이라면 그들이 인접하게 선택되었는지 찾아주고, 4명 미만이라면 인접 여부를 구할 필요가 없다. <- 백트래킹

 

인접 여부는 BFS를 활용하였는데, 원해 하던 방법을 거꾸로 이용하였다. 먼저 선택된 아이들의 visited를 true로 바꿔주고 탐색하면서 false로 바꿔주었다.

---

[JAVA 코드]

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	static int result;
	static int [] selected = new int [7];
	static int [][] map = new int [5][5];
	static boolean [][] visited;
	static int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1}; 
	
	static class Point {
		int r, c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) throws IOException {
		for(int r = 0; r < 5; r++) {
			String line = br.readLine();
			for(int c = 0; c < 5; c++) {
				if(line.charAt(c) == 'S') {
					map[r][c] = 1; // 이다솜파
				} else {
					map[r][c] = 0; // 임도연파
				}
			}
		}
		
		comb(0, 0);
		
		System.out.println(result);
	}

	private static void comb(int idx, int start) {
		if(idx == 7) {
			// 일단 뽑은 아이들 체크
			int s = 0, y = 0; // 이다솜파, 임도연파
			visited = new boolean [5][5];
			for(int i = 0; i < 7; i++) {
				int r = selected[i] / 5;
				int c = selected[i] % 5;
				
				if(map[r][c] == 1) s++;
				else			   y++;
				visited[r][c] = true;
			}
			
			// 이다솜파가 4명 이상인 경우에만 연결 체크
			if(s >= 4) {
				if(isConnected()) {
					result++;
				}
			}
			return;
		}
		
		for(int i = start; i < 25; i++) {
			selected[idx] = i;
			comb(idx + 1, i + 1);
		}
	}

	private static boolean isConnected() {
		Queue<Point> Q = new LinkedList<>();
		
		Q.add(new Point(selected[0] / 5, selected[0] % 5));
		visited[selected[0] / 5][selected[0] % 5] = false; // 선택 해제
		int cnt = 0; // 인접해있는 아이가 몇 명인지
		
		while(!Q.isEmpty()) {
			Point now = Q.poll();
			cnt++;
			
			for(int i = 0; i < 4; i++) {
				int nr = now.r + dr[i];
				int nc = now.c + dc[i];
				
                // 인덱스를 벗어나거나, 선택된 아이가 아닌경우
				if(nr < 0 || nr >= 5 || nc < 0 || nc >= 5|| !visited[nr][nc]) continue;
				
				Q.add(new Point(nr, nc));
				visited[nr][nc] = false; // 선택 해제
			}
		}
		
		if(cnt == 7) return true;
		else		 return false;
	}
}