[백트래킹] C11 백준 1941 소문난 칠공주 풀이

문제

• 1941

풀이 과정

• 내가 뽑아낸 조건은 다음과 같다
  • 7명 여학생을 뽑는데, S가 4이상이여야 함 -> 종료 조건이네
  • 7명 자리는 상하좌우 인접해야 함 -> 오 그럼 bfs?
  • 모든 경우의 수를 출력하라 -> 그럼 시작점이 전구간?
• 그래서 아래와 같은 코드로 작성했는데 개같이 틀렸다

틀린 코드

• 접근 방식은 bfs를 각 좌표에서 시작해서 연결된 7명을 확인하고 맞으면 result++ 하는 단순한 방식이었는데,
• 우리의 선생님 chatgpt에게 물어보니 구현방식의 문제와 조건검증의 불완전함 이 있단다..
  • 무튼 비효율적이고 쓰레기 코드라고 비난 받음

#include <stdio.h>

#define MAX 5

typedef struct Que {
    int x;
    int y;
    int num;
    int total;
} Q;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

char girl[MAX][MAX];
int visit[MAX][MAX];
int result;

Q que[MAX*MAX];
int front;
int rear;

void enqueue(int x, int y, int num, int total) {
    que[rear].x = x;
    que[rear].y = y;
    que[rear].num = num;
    que[rear].total = total;
    rear++;
}

Q dequeue() {
    return que[front++];
}

void bfs() {
    while (front < rear) {
        Q cur = dequeue();
        
        if (cur.total == 7 && cur.num <= 3) {
            result++;
            continue;
        }
        
        for (int i=0; i<4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && visit[nx][ny] == 0) {
                visit[nx][ny] = 1;
                
                if (girl[nx][ny] == 'S') {
                    enqueue(nx, ny, cur.num, cur.total+1);
                } else if (girl[nx][ny] == 'Y' && cur.num < 3) {
                    enqueue(nx, ny, cur.num+1, cur.total+1);
                }
            }
        }
    }
}

int main() {
    for (int i=0; i<5; i++) {
        scanf("%s", girl[i]);
    }
    
    for (int i=0; i<5; i++) {
        for (int j=0; j<5; j++) {
            
            for (int a=0; a<5; a++) {
                for (int b=0; b<5; b++) {
                    visit[a][b] = 0;
                }
            }
            
            front = 0;
            rear = 0;
            
            visit[i][j] = 1;
            enqueue(i, j, (girl[i][j] == 'Y'), 1);
            bfs();
        }
    }
    
    printf("%d", result);
    
    return 0;
}

정답 코드

• 아.. 정답코드를 보고 느낀건 생각해보니 위와 같은 코드로 자면 중복이 있겠구나.. 라는거 였고 확실히 불필요한 코드로 계속 bfs를 돌리다보니 효율이 떨어지겠다 싶었다
  • 근데 어차피 접근방식부터 글러먹은 코드(ㅠㅠ)
• 무튼 정답 코드의 접근 방식은 먼저 7명의 조합을 생성한 뒤 이 조합들이 연결되어있는지 판단하면 된다

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX 5
#define TOTAL 25
#define COMB 7

char board[MAX][MAX + 1]; // 입력 배열 (문자열 입력을 위해 +1)
int ans = 0;              // 최종 결과
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool mask[TOTAL]; // 조합을 위한 배열

void swap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

bool next_permutation(bool *arr, int n) {
    int i = n - 1;
    while (i > 0 && arr[i - 1] >= arr[i]) i--;
    if (i <= 0) return false;

    int j = n - 1;
    while (arr[j] <= arr[i - 1]) j--;
    swap(&arr[i - 1], &arr[j]);

    j = n - 1;
    while (i < j) {
        swap(&arr[i], &arr[j]);
        i++;
        j--;
    }
    return true;
}

void bfs(int start_x, int start_y, bool isp7[MAX][MAX], int *adj, int *dasom) {
    bool vis[MAX][MAX] = {false}; // 방문 확인 배열
    int queue[MAX * MAX][2];      // BFS 큐
    int front = 0, rear = 0;

    queue[rear][0] = start_x;
    queue[rear++][1] = start_y;
    vis[start_x][start_y] = true;

    while (front < rear) {
        int x = queue[front][0];
        int y = queue[front++][1];
        (*adj)++;
        if (board[x][y] == 'S') (*dasom)++;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx >= 0 && nx < MAX && ny >= 0 && ny < MAX && !vis[nx][ny] && isp7[nx][ny]) {
                vis[nx][ny] = true;
                queue[rear][0] = nx;
                queue[rear++][1] = ny;
            }
        }
    }
}

void solve() {
    do {
        bool isp7[MAX][MAX] = {false};
        int first_x = -1, first_y = -1;

        for (int i = 0; i < TOTAL; i++) {
            if (!mask[i]) {
                int x = i / MAX;
                int y = i % MAX;
                isp7[x][y] = true;
                if (first_x == -1) {
                    first_x = x;
                    first_y = y;
                }
            }
        }

        int adj = 0, dasom = 0;
        bfs(first_x, first_y, isp7, &adj, &dasom);

        if (adj == 7 && dasom >= 4) {
            ans++;
        }
    } while (next_permutation(mask, TOTAL));
}

int main() {
    for (int i = 0; i < MAX; i++) {
        scanf("%s", board[i]);
    }

    for (int i = 0; i < COMB; i++) mask[i] = false;
    for (int i = COMB; i < TOTAL; i++) mask[i] = true;

    solve();

    printf("%d\n", ans);
    return 0;
}

• 이 문제는 결국 못 풀었으므로 다음에 다시 시도해보도록 하겠다.