1941 소문난 칠공주

dfs 완전탐색 문제

1. visit를 7개의 순열로 하나씩 검사해야 하는데 다 만들기에는 너무 빡세다. 외판원 순회에서 적용했던 비트마스크 visit 변수를 놓는다면 쉽게 해결할 수 있다. 즉 (1<<25) 크기의 배열을 만든다음 방문한 것은 true로 놓으면서 방문 검사를 할 수 있다. 예를 들어 1 2 7 8 노드를 방문했다면 visit[(1<<1) | (1<<2) | (1<<7) | (1<<8)] = true로 놓을 수 있다

2. 그 다음은 디버깅을 통해 발견했는데, 오직 한 점에서만 확장되는 것이 아니라 같은 집합의 요소들도 확장할 수 있다는 점이었다. 따라서 한 번 움직일 때 집합 노드를 모두 움직여서 탐색했다.

 

문제: https://www.acmicpc.net/problem/1941  

https://github.com/surinoel/boj/blob/master/1941.cpp