[백준] 1941 소문난 칠공주

 

---

소문난 칠공주를 결성할 수 있는 모든 경우의 수를 구하는 문제이다. 브루트 포스, 백트래킹 알고리즘 유형에 해당한다.

 

단, 소문난 칠공주는 가로 또는 세로로 모두 인접해야하며, 이다솜파가 과반수(4)이상 이어야 한다.

 

• 여학생반의 크기는 5*5 크기로 고정되어 있기 떄문에 학생들을 0 ~ 24로 인덱싱한다.
• n번 학생의 위치는 (n / 5,  n%5 )에 위치한다.
• DFS를 통해 0번 부터 24번 학생까지 순회한다.
• 현재 학생을 I라고 하면 I 학생은 이다솜파, 임도연파 중 하나이며 소문난 칠공주에 포함할 지 결정한다.
• 7명을 모두 소집한 경우 모두 인접한지 확인한다.
• 시작점을 기준으로 상, 하, 좌, 우 인접한 노드를 DFS로 방문하여 인접한 경우 카운트를 1 증가시키고 7이 되는 경우 모두 인접한 것으로 한다.

 

Python