boj 1941 java

[BaekJoon] 1941번 소문난 칠공주 (Java) 문제 풀이 [Gold 3]

문제https://www.acmicpc.net/problem/1941 어떻게 풀 것인가?이 문제는 백트래킹(Backtracking) 을 이용해서 풀었다.우선 문제를 잘 읽어보면 배열의 크기와 조건이 크지 않음을 알 수 있다.즉, 브루트포스(완전 탐색) 및 백트래킹을 사용해도 시간 초과 없이 해결할 수 있다.따라서, 25명 중 7명을 선택하는 조합(combination)을 수행한 후,선택된 7명이 서로 연결되어 있는지 확인하고,최소 4명이 ‘이다솜파’(S)인지 확인하는 방식으로 접근했다. 풀면서 놓쳤던점DFS 탐색 방식의 오류단순히 DFS로 인접한 학생을 탐색하는 것이 아니라, 25명 중 7명을 조합으로 선택한 후, 그 7명이 하나의 연결된 그룹인지 확인해야 했다.즉, DFS로 직접 7명을 선택하면 모든 ..