1. 문제
설명
총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.
위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.
- 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
- 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
- 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
- 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.
여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.
입력
'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.
출력
첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.
2. 풀이
일반적인 BFS, DFS 방식으로는 해결할 수 없는 문제입니다.
저도 처음에 쉽게 봤다가 큰 코 다친 문제입니다.
아래와 같은 예시와 가능한 경우의 수를 보면 음? 하게 됩니다.
예시)
YYYYY
SYSYS
YYYYY
YSYYS
YYYYY
경우1)
YYYYY
SYSYS
YYYYY
YSYYS
YYYYY
경우2)
YYYYY
SYSYS
YYYYY
YSYYS
YYYYY
十, T 같은 모양이 만들어지는데 이를 어떻게 만들어야할지 고민을 많이 했습니다.
BFS는 호수에 돌을 던질 때 생기는 파동 마냥 퍼지고,
DFS는 뱀 모양밖에 못 만드니 난감했습니다.
근데 여러분 사실 2차원 배열은 1차원 배열을 길게 늘린 모양이라는 사실을 아십니까?
위 예제를 실제 컴퓨터가 데이터를 저장하고 있는 형태로 만들어 생각하면 문제가 한층 쉬워집니다.
예시)
YYYYY|SYSYS|YYYYY|YSYYS|YYYYY
경우1)
YYYYY|SYSYS|YYYYY|YSYYS|YYYYY
경우2)
YYYYY|SYSYS|YYYYY|YSYYS|YYYYY
어떻습니까? 그저 25개의 좌표 중에서 7개의 좌표를 고르는 조합 문제로 바뀌었습니다.
저도 2차원 배열은 1차원 배열을 길게 늘린 모양이란 사실은
최근에 컴퓨터 구조, C언어를 공부하면서 깨달은 사실인데요,
항상 컴퓨터가 이해할 수 있게 컴퓨터 친화적으로 생각해야
문제를 쉽게 해결할 힌트를 얻는 듯 합니다.
시간 복잡도는 조합 공식에 의해 대략 48만 정도 나오기 때문에 위 로직을 사용해도 됩니다.
3. 전체 코드
#define MAX 5
#define PICK_NUM 7
#include <bits/stdc++.h>
using namespace std;
int visited[MAX][MAX];
int seated[MAX][MAX];
char seat[MAX * MAX];
int my[4] = { 0, 1, 0, -1 };
int mx[4] = { 1, 0, -1, 0 };
int startY, startX;
queue<pair<int, int>> q;
// y 좌표로 변환
int calcY(int num) {
return floor(num / MAX);
}
// x 좌표로 변환
int calcX(int num) {
return num % MAX;
}
// 임도연일 때 개수 증가
int getYcount(int num) {
return seat[num] == 'Y' ? 1 : 0;
}
// 자리가 연결돼있는지 확인
int getConnectCount(int y, int x) {
int ret = 1;
visited[y][x] = 1;
q.push({ y, x });
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
if (ny < 0 || ny >= MAX || nx < 0 || nx >= MAX) continue;
if (!seated[ny][nx] || visited[ny][nx]) continue;
ret += getConnectCount(ny, nx);
}
return ret;
}
int slove(int depth, int start, int Ycount) {
// 가지 치기, 임도연이 4명 이상일 때
if (Ycount >= 4) return 0;
// 기저 사례, 7명을 뽑았을 때
if (depth == PICK_NUM) {
// 서로 연결됐는지 확인
int ret = getConnectCount(startY, startX) == PICK_NUM ? 1 : 0;
// visited 배열 초기화
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
visited[y][x] = 0;
}
return ret;
}
int ret = 0;
for (int i = start; i < MAX * MAX; i++) {
int y = calcY(i);
int x = calcX(i);
seated[y][x] = 1;
ret += slove(depth + 1, i + 1, Ycount + getYcount(i));
seated[y][x] = 0;
}
return ret;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < MAX * MAX; i++) cin >> seat[i];
int ans = 0;
// 7개를 고를 수 있는 경우까지만 탐색
for (int i = 0; i <= MAX * MAX - PICK_NUM; i++) {
// 처음엔 연결됐는지 확인할 시작 좌표를 정하고 탐색
startY = calcY(i);
startX = calcX(i);
seated[startY][startX] = 1;
ans += slove(1, i + 1, getYcount(i));
seated[startY][startX] = 0;
}
cout << ans;
return 0;
}참고로 칠공주 좌석을 만들어나갈 때, 인접한 여학생이 있는지 확인하면서 만들면 안 됩니다.
탐색 당시엔 인접하지 않아도, 기저 사례에선 인접할 수 있기 때문입니다.
