소문난 칠공주

예상 난이도 : 6 / 10

이번 문제는 '소문난 칠공주'(https://www.acmicpc.net/problem/1941) 입니다.

이 문제가 좋다고 생각하는 이유는 'dfs와 bfs와 백트래킹을 모두 연습해 볼 수 있는 문제'이기 때문입니다.

개인적으로 너무 좋다고 생각합니다.

우선 25개의 자리 중 7자리를 선택하는 것부터 시작해보겠습니다. 

이 문제는 '완전 탐색의 기본' 이라는 글을 완전히 숙지했다는 가정하에 설명합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
char mp[5][5];
bool chk[5][5];
 
int sol(int y, int x, int som, int yon) {
    if (som + yon == 7) {
        int cnt = 1;
        queue<pii> q;
        bool chk2[5][5] = {};
        q.push({ y,x });
        chk2[y][x] = true;
        while (!q.empty()) {
            pii f = q.front();
            q.pop();
            for (int dir = 0; dir < 4; dir++) {
                int ny = f.first + dy[dir], nx = f.second + dx[dir];
                if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5 || chk2[ny][nx] || !chk[ny][nx]) continue;
                q.push({ ny,nx });
                chk2[ny][nx] = true;
                cnt += 1;
            }
        }
        return (cnt == 7 ? 1 : 0);
    }
 
    int ret = 0;
    for (int i = y; i < 5; i++) {
        int j = (i == y ? x + 1 : 0);
        for (; j < 5; j++) {
            if (mp[i][j] == 'Y' && yon + 1 >= 4) continue;
            chk[i][j] = true;
            if (mp[i][j] == 'Y') ret += sol(i, j, som, yon + 1);
            else ret += sol(i, j, som + 1, yon);
            chk[i][j] = false;
 
        }
    }
 
    return ret;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> mp[i][j];
 
 
    cout << sol(0, -1, 0, 0);
 
 
    return 0;
}
 

이번에는 문제가 어렵다고 쉬운 편은 아니라고 판단하여 소스코드를 첨부합니다.

자리를 고르는 부분을 제 코드가 익숙치가 않다면 0부터 24까지 중에 7개를 고른다고 for문을 하나로 수정해도

무방합니다. 아래와 같은 식으로 말이죠. 그렇게 한 다음 행과 열 값을 다시 구해주기만 하면 됩니다.

저는 그것보다 위 같은 방법이 좋아요.

for (int i = cur + 1; i < 25; i++) {
        int x = i / 5, y = i % 5;
        //...
}

36번째 줄을 추가한 것은 '7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.'는 조건을 사용한 것입니다.

if 문을 추가함으로써 효율성을 개선할 수 있겠죠. 답이 될 가능성이 전혀 없는 곳은 미리 갈 필요가 없잖아요!!

문제마다 답이 될 가능성을 미리 판단할 수 없는 경우도 존재하니 확실할 경우만 판단해서 사용해야 합니다.

7자리를 모두 골랐다면 12번째 줄 if 문이 참이 되면서 안으로 들어가 내가 고른 자리가 모두 인접한지 확인하기 위해서 bfs를 수행합니다. 

만약 7자리가 모두 붙어 있다면 cnt가 7이 되겠죠. 그럼 1을 리턴하고 아니면 0을 리턴하여 경우의 수를 하나하나 모아서 돌아갑니다

끝!