티스토리 뷰

PS/BOJ

[BOJ] 백준 1941번: 소문난 칠공주

박트리 2017. 3. 27. 23:42

소문난 칠공주


문제


상하좌우로 연결된 크기가 7이고 S가 4 이상 포함된 컴포넌트의 개수를 세는 문제이다.


문제 풀이


한 점을 기준으로 단순 bfs나 dfs로는 십자가 모양 등을 찾을 수가 없다. 따라서 25개의 학생 중에서 7명을 뽑고 여기서 S가 4 이상 포함되었는지 그리고 모두 연결되었는지를 판단하는 방식으로 구현하였다. \( \begin{pmatrix} 25 \\ 7 \end{pmatrix} = 480,700\) 이고 7명 중 한 명에서 dfs로 최대 컴포넌트 크기가 7인 경우만 가능한 경우로 판단하여 정답을 구하면 된다. \( O(480,700*25) \) 로 해결 가능하다.


소스 코드



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함