[백준] 1941번 소문난 칠공주 (자바 풀이)

문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 이 문제는 단순히 BFS, DFS를 사용하면 해결하기 매우 힘들다. 모든 자리에서 4방향을 모두 조사하는 식으로 탐색하면 경우의 수가 너무 많아 시간 초과가 발생한다. 따라서 조합을 사용하여 해결하는 편이 좋다. 25개의 자리 중 7개를 선택하는 경우의 수는 25C7 = 480700 으로 작은 편이다. 1. 25개의 자리 중 7개를 뽑는다. 2. 해당 7개의 자리가 모두 상하좌우로 연결되어..

원문링크 : [백준] 1941번 소문난 칠공주 (자바 풀이)