C - [백준 1941] 소문난 칠공주 (feat. 백트래킹, DFS)

참고 포스트

2025.01.07 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

[알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

 

https://www.acmicpc.net/problem/1941

BOJ 1941 소문난 칠공주

 

"소문난 칠공주" 문제는 주어진 5x5 격자에서 7명의 학생을 선택하는 조합 문제입니다. 선택된 학생들은 다음 조건을 만족해야 합니다:

1. 7명 중 최소 4명은 이다솜파('S')여야 합니다.
2. 선택된 학생들은 반드시 인접(상하좌우)해야 합니다.

---

Checkpoint

 

해당 문제는 백트래킹에 대한 확실한 개념을 잡게 해주었던만큼 N과 M 시리즈 못지 않게 정말 중요한 문제라고 생각합니다. 여태까지 알고리즘 문제를 풀면서 시간을 가장 많이 소요한 문제이기도 합니다. (시작부터 벽 느끼고 해설을 봤던 하노이 탑 제외)

 

 

문제 힌트를 보고 알고리즘 설계 단계에서 부터 막혀서 보류해놓았던 문제입니다. 기존에 제가 백트래킹을 활용한 방법은 N-Queen 문제를 기반으로 상하좌우의 방향성을 두면서 경우의 수를 따져나가는 것이었습니다.

그 방법을 적용했을 경우, 현 위치와 인접해 있는 곳을 한칸 한칸씩 전진해가면서 7명을 채운 후 S(이다솜파)가 4개 이상있는지 확인 할 수 있기 때문에 힌트의 첫 번째 케이스는 구현할 수 있습니다. 하지만 이 알고리즘 설계의 문제점은 힌트의 두번째 케이스에 있습니다. 이유는, DFS에 방향성을 부여하면 T 자, + 자, X자 등 교차 지점이 발생하면 재방문하기 힘들다는 것입니다 (지금 알고 있는 수준에서는 불가능한 구현 방법). 해당 방법일 경우 visited 를 통해 방문이 안된 곳만 찾아서 전진하는 방식인데 교차지점이라는 것은 방문한 곳을 재체 방문해야하는 경우이기 때문입니다.

 

하지만 제가 간과하고 있던 점이 있었습니다. 백트래킹은 연속적인 처리에 집중 된 알고리즘이 아니라, 모든 경우의 수를 구하는 핵심에 특정 알고리즘을 삽입하여 원하는 동작 및 경우의 수만 처리하는 알고리즘이라는 것입니다.

 

해당 내용은 이 포스트를 참고하면 됩니다.

2025.01.07 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

[알고리즘] 백트래킹과 DFS: 문제 요구사항에 맞춘 설계 방법 (feat. 알고리즘 문제 유형)

 

결과적으로 백트래킹으로 조합을 구한 후, 구한 7개의 수가 서로 연결되어있는지 확인하면 됩니다.

 

해당 설계가 가능했던 이유는 "조합 + 그래프의 인접 요소" 두 개념을 인지하고 있기 때문입니다.

 

문제로 따지면,

BOJ_6603_로또 +  BOJ_11724 연결 요소의 개수 두 문제의 원리를 파악하면 이 문제도 쉽게 해결할 수 있습니다.

 

https://rnasterofmysea.tistory.com/76

 

 

https://rnasterofmysea.tistory.com/48

C - [백준 11724] 연결 요소의 개수 (feat. 배열)

 

---

문제 풀이 접근

1. 백트래킹을 이용한 조합 탐색
   25개의 칸 중 7개의 칸을 선택하여 모든 조합을 생성합니다. 각 조합이 조건을 만족하는지 확인합니다.
2. 조건 확인
   • 선택된 칸들 중 'S'가 4개 이상인지 확인합니다.
   • 선택된 칸들이 모두 연결되어 있는지 확인합니다. 이는 BFS 또는 DFS를 통해 해결할 수 있습니다.
3. 최적화
   • 'S'의 개수가 4개 미만이라면 조합을 더 탐색하지 않도록 가지치기를 수행합니다.

---

구현 코드

#include <stdio.h>
#define MAX 5


char class[MAX][MAX+1];
char com[7][2];
int result = 0;
// bfs 변수
int visited[7];
int queue[7][2];
int front = 0;
int rear = 0;
// 상하좌우 이동 방향 (x, y)
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};


// 큐 삽입
void enqueue(int x, int y) {
    queue[rear][0] = x;
    queue[rear][1] = y;
    rear++;
}
// 큐 제거
void dequeue(int *x, int *y) {
    *x = queue[front][0];
    *y = queue[front][1];
    front++;
}

void bfs(){
    front = 0;
    rear = 0;
    for(int i = 0 ; i < 7; i ++){
        visited[i] = 0;
    }
    
    int count = 1;
    enqueue(com[0][0],com[0][1]);
    visited[0] = 1;
    while(front < rear){
        int x, y;
        dequeue(&x, &y);

        for(int i = 0 ; i < 4 ; i ++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            for(int j = 0; j < 7; j ++){
                 if(com[j][0] == nx && com[j][1] == ny && !visited[j]){
                     enqueue(com[j][0], com[j][1]);
                     visited[j] = 1;
                     count ++;
                 }
            }
        }
        
    }
    if(count == 7){
        result++;
    }
}

void combination(int depth, int idx, int count_s){
    if(depth == 7){
        if(count_s >= 4){
        bfs();
        }
        return;
    }
    for(int i = idx; i < MAX * MAX ; i ++){
        int x = i % 5;
        int y = i / 5;
        com[depth][0] = x;
        com[depth][1] = y;
        // 'S' 카운트 증가
        if (class[y][x] == 'S') {
            combination(depth + 1, i + 1, count_s + 1);
        } else {
            combination(depth + 1, i + 1, count_s);
        }   

    }
}

int main() {
    for(int i = 0; i < MAX; i++){
        scanf("%s", class[i]);
    }
    combination(0,0,0);
    printf("%d", result);
    return 0;
}

---

코드 분석

1. 입력 처리 및 상수 정의

#define MAX 5

char class[MAX][MAX+1];
char com[7][2];
int result = 0;

• class 배열에 5x5 격자 데이터를 저장합니다.
• com 배열은 선택된 7개의 좌표를 저장합니다.
• result는 조건을 만족하는 조합의 개수를 저장합니다.

---

2. BFS를 통한 연결 확인

int visited[7];
int queue[7][2];
int front = 0;
int rear = 0;

int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

• queue는 BFS 탐색을 위한 큐입니다.
• dir 배열은 상하좌우 이동을 위한 방향 벡터입니다.

BFS 구현

void bfs() {
    front = 0;
    rear = 0;
    for(int i = 0 ; i < 7; i++) {
        visited[i] = 0;
    }
    
    int count = 1;
    enqueue(com[0][0], com[0][1]);
    visited[0] = 1;

    while(front < rear) {
        int x, y;
        dequeue(&x, &y);

        for(int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            for(int j = 0; j < 7; j++) {
                if(com[j][0] == nx && com[j][1] == ny && !visited[j]) {
                    enqueue(com[j][0], com[j][1]);
                    visited[j] = 1;
                    count++;
                }
            }
        }
    }

    if(count == 7) {
        result++;
    }
}

• BFS를 통해 선택된 7개의 좌표가 연결되어 있는지 확인합니다.
• 큐를 이용하여 연결된 칸을 탐색하며, 방문한 칸의 개수가 7개이면 result를 증가시킵니다.

---

3. 조합 생성 (백트래킹)

void combination(int depth, int idx, int count_s) {
    if(depth == 7) {
        if(count_s >= 4) {
            bfs();
        }
        return;
    }

    for(int i = idx; i < MAX * MAX; i++) {
        int x = i % 5;
        int y = i / 5;
        com[depth][0] = x;
        com[depth][1] = y;

        if (class[y][x] == 'S') {
            combination(depth + 1, i + 1, count_s + 1);
        } else {
            combination(depth + 1, i + 1, count_s);
        }   
    }
}

• 백트래킹을 사용하여 25개의 칸 중 7개의 칸을 선택합니다.
• 선택된 칸 중 'S'의 개수를 count_s로 관리하여 조건을 만족하는 경우만 BFS를 호출합니다.

---

4. 메인 함수

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

    combination(0, 0, 0);
    printf("%d", result);
    return 0;
}

• 5x5 격자 데이터를 입력받아 class 배열에 저장합니다.
• combination 함수를 호출하여 가능한 조합을 탐색합니다.
• 최종 결과를 출력합니다.

---

주요 로직 설명

1. 조합 생성
   combination 함수는 백트래킹을 사용하여 모든 가능한 조합을 탐색합니다.
   • 'S'의 개수가 4개 미만이면 더 이상 탐색하지 않도록 가지치기를 수행합니다.
2. 연결 확인
   선택된 좌표가 모두 연결되어 있는지 bfs 함수로 확인합니다.
   • BFS를 사용하여 연결된 칸의 개수를 세고, 7개가 되지 않으면 조건을 만족하지 않습니다.
3. 최적화
   • 백트래킹 중 'S'의 개수를 관리하여 불필요한 탐색을 줄입니다.
   • BFS를 통해 연결 여부를 빠르게 확인합니다.

---

예제 입력 및 출력

입력

YYYYY
SYSYY
YYYYY
YYYYY
YYYYY

출력

2

위 입력은 총 2개의 조건을 만족하는 조합이 있음을 보여줍니다.

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.