링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu예전 기억으로는, 삼성 SW 역량 테스트 준비용 샘플 문제가 하나밖에 없었는데 뭔가 많이 추가된 모양이다.이번 문제는 그 중 하나이다.삼성 SW 역량 테스트에는 이런 백트래킹류의 탐색 문제가 자주 나오는 것 같다.문제문제를 요약하자면, 세로 길이가 D이고 가로 길이가 W인 2차원 평면에서, 특정 조건에 맞추기 위해 어떤 행을 모두 A(0) 또는 B(1)로 바꾸는 횟수를 최소로 하고 싶다는 것이다.여기서 조건은, 모든 세로줄에서 같은 종류끼리 K개 이상 연속으로 붙어 있으면 되게 만드는 것이다. 어떤 행을 선택하는 조합이 여러개이므로 ..

링크: https://www.acmicpc.net/problem/17142 문제 연구소에 이미 존재하는 바이러스들 중 \(m~(2\le m \le 10)\)개를 활성 상태로 바꾸어 바이러스를 퍼뜨리는 문제이다. 그 때, 연구소의 모든 빈칸에 바이러스가 퍼지게 하는 최소 시간을 구해야 한다. 풀이 연구소에 존재하는 바이러스 들 중 \(m\)개를 골라야한다. DFS 같은 방법으로 고를 수 있지만, next_permutation을 사용하면 간단하다. 4개 중 2개를 고르는 조합은 0011 → 0101 → 0110 → 1001 → 1010 → 1100 순으로 진행된다. 이런 특징을 사용하여 매번 적당히 \(m\)개를 선택하여 플러드 필(Flood Fill, BFS)을 한다. 모든 빈칸을 방문한다면 그 때의 탐색..