1941번

1941번 - 소문난 칠공주

처음에 단순히 dfs 백트래킹으로 풀려고 했으나, 십자가 중간에 튀어나온 모양은 dfs로 풀기가 어려웠다.

삼성에서 기출문제로 나왔던 문제가 있었는데, 그 문제는 dfs 로 돌리고 남은 모양은 직접구해서 맞추는 문제였다.

하지만 이 문제는 그러한 방식으로 조차 풀 수가 없었다. 그래서 다른 사람들의 코드를 봤다.

로직은 항상 25개 중에서 7개를 뽑는 식이기 때문에 go 함수를 통해서 7개의 수를 뽑는다.

이때 가지치기를 통해서 Y가 4개 이상이면 return 해주는 방식으로 문제를 푼다.

여기서 배운 스킬은 맵을 0 ~ 24까지 숫자로 놓으면 x,y 좌표는 [번호/n][번호%n] 이 된다는 점이었다.

이를 가지고 7개의 수를 뽑는 방식도 쉽게 풀 수 있었다.

그리고 뽑은 7개의 수는 dfs 혹은 bfs를 통해서 연결되어 있는지만 확인해주면 되는 문제로 쉽게 풀 수 있었다.

아이디어 싸움이었던 문제였다.

<정답 코드>

#include<iostream>
#include<string.h>
using namespace std;
char map[5][5];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int ans = 0;
int op[7];
bool check[5][5];
void dfs(int x, int y)
{
    check[x][y] = true;
 
    for (int d = 0; d < 4; d++)
    {
        int nx = x + dx[d];
        int ny = y + dy[d];
 
        if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5 && !check[nx][ny])
        {
            dfs(nx, ny);
        }
    }
 
}
void go(int n,int k,int y)
{
    if (y >= 4)
    {
        return;
    }
    if (n == 7)
    {
        memset(check, true, sizeof(check));
        for (int i = 0; i < 7; i++)
        {
            int x = op[i] / 5;
            int y = op[i] % 5;
 
            check[x][y] = false;
        }
 
        int cnt = 0;
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                if (!check[i][j])
                {
                    cnt++;
                    if (cnt >= 2)
                    {
                        return;
                    }
                    dfs(i, j);
                }
            }
        }
 
        ans += 1;
        return;
    }
 
    for (int i = k+1; i <= 24; i++)
    {
        op[n] = i;
        if (map[i / 5][i % 5] == 'Y')
        {
            go(n + 1, i, y + 1);
        }
        else
        {
            go(n + 1, i, y);
        }
    
    }
    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            cin >> map[i][j];
        }
    }
    
    go(0,-1,0);
 
    cout << ans << "\n";
 
    return 0;
}