1941 소문난 칠공주
-
백준 1941 소문난 칠공주Algorithm/BOJ 2021. 6. 6. 16:50
출처: https://www.acmicpc.net/problem/1941 분류: brute force 접근방식 처음엔 그냥 bfs, dfs로 풀 수 있겠거니 했으나.... 점점 어라? 어라..? 어라....????!! 하며 쉽지 않았던 문제였습니다. 중복을 어떻게 줄여줘야할지 도통 감이 오질 않더라구요.. 결국은 다음와 같은 과정으로 해결했습니다. 1. 각 칸을 0~24로 두고, 0~24 중 7개를 선택하는 조합을 구한다. (약 48만개) 2. 조합에서 S가 4명 이상인지 확인한다 3. 조합이 모두 인접해있는지 확인한다. 1, 2번까지는 어렵지 않게 구할 수 있을 거 같은데 3번이 살짝 까다롭네요. 3번은 만든 조합의 0번부터 시작해 인접한 수가 조합안에 있는지 확인하고 queue에 담아주면서 탐색하는 ..