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

문제

출처 : www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

5*5그리드에 학생들의 파가 주어진다. (이다솜파 : S, 임도연파 : Y)

이다솜은 자신의 파를 늘리기위해 소문난 칠공주를 결성하기로했다.

칠공주가 되기위해선 3가지 조건이 필요한데,

 

1. 칠공주에 속하는 학생들은 서로 인접해있어야한다. 

2. 7명의 학생으로 구성되어야한다.

3. 이다솜파보다 임도연파가 더 많아야한다.

 

이때, 소문난 칠공주를 결성하는 모든 경우의수를 구하는 문제다.

 

풀이

푸는데 2일이나 걸린문제다...

 

맵의 크기가 크지않아서, 완전탐색으로도 풀수있다. 구현이 어려웠는데, 일반적인 DFS로 연결된 학생을 타고 들어가면 안되고, (T자 모양에서 반례가 생긴다) 25명의 학생중 7명을뽑아서 그 학생들이 인접해있는지 판단해야한다. 

 

처음엔 학생의 최대수가 총 25명 이길래 비트마스킹으로 체크해서 중복을 피할려했었지만 배열 크기 초과로 컴파일 에러를 받았다. 생각해보니 애초에 뽑을때 중복을 피해서 뽑으면 되서 중복체크를 해줄필요도없었다...

 

2차원 배열을 1차원으로 바꿔줬다. 이렇게 하면 구현할때 편한점이 많은데, 

- 누구 뽑았는지 체크(경로찾기로 구현해서 정확히 7번만에 찾는다) 

- 총 25명의 학생중 중복을 피해 7명 뽑기 (2차원으로 하면 중복을 피하기위해 행,열 따로 계산해서 시작 지점을 바꿔줘야하는데, 1차원으로 하면 전 idx+1부터 시작하면 중복을 피할수있다.)

 

1. 25명의 학생중 7명의 학생을 중복을 피해 뽑는다.

 

2. 뽑은 학생중 'S'인 학생의 갯수를 찾는다.

 

3. 'S'인 학생의 수가 4명 이상이라면, 모두 연결되어있는지 확인한다.

- BFS를 이용해서 4방향으로 이동하며 확인해줬다.

 

4. 모두 연결되어있다면 경우의수 + 1

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1941%20%EC%86%8C%EB%AC%B8%EB%82%9C%20%EC%B9%A0%EA%B3%B5%EC%A3%BC/main.cpp

devxb/JJUNalgo