ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [백준/BOJ] 1941번 소문난 칠공주 (C++)
    알고리즘 문제풀이/백준 2020. 12. 1. 13:48

    www.acmicpc.net/problem/1941

     

    1941번: 소문난 칠공주

    총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작

    www.acmicpc.net

    새롭게 알게된 점

    십자가 모양은 일반적인 DFS + 백트래킹으로 문제를 해결할 수 없다.

    DFS와 BFS를 같이 쓰는 문제가 존재한다. (이번 문제가 그러했음)

     

    문제를 해결하는 순서는 다음과 같습니다.

    1. 학생 25명중 7명을 선택하는 조합을 DFS를 통해 구하기

    2. 해당 조합에서 다솜이파 학생이 4명 이상인지 확인하는 isMoreThanFour() 함수 구현

    3. 해당 조합에서 선택된 학생이 인접한지 확인하는 isAdjacent() 함수 구현

    4. 2번 3번을 모두 만족하는 조합이라면 answer++

     

    선택된 학생이 인접한지 확인하는 것은 BFS를 사용했습니다. 포인트는 큐가 선택된 학생에 한해서만 탐색하기 위해 checked 배열에 선택된 학생의 위치를 체크하는 것입니다. 

     

    #include <iostream>
    #include <queue>
    #include <cstring>
    using namespace std;
    
    char map[5][5];
    bool pick[25];
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    int answer;
    
    // 다솜이파 학생이 4명 이상인지 확인
    bool isMoreThanFour() {
        int sum = 0;
        for(int i = 0; i < 25; i++) {
            // 행 인덱스 : 학생 번호 / 5, 열 인덱스 : 학생 번호 % 5
            // 다솜이파 학생인 경우 sum++
            if(pick[i] && map[i / 5][i % 5] == 'S') sum++;
        }
        if(sum >= 4) return true;
        else return false;
    }
    
    // 학생들끼리 인접한 조합인지 확인
    bool isAdjacent() {
        queue<pair<int, int > > q;
        bool visit[5][5]; // 방문 여부 체크
        bool checked[5][5]; // 이전에 선택된건지 체크
        
        // 초기화
        memset(visit, false, sizeof(visit));
        memset(checked, false, sizeof(checked));
        
        bool first = true;
        for(int i = 0; i < 25; i++) {
            if(pick[i]) {
                // 선택된 학생만 큐를 돌기 위해 checked 배열에 미리 체크
                checked[i / 5][i % 5] = true;
                // 처음 선택된 학생만 큐에 넣어줌 (큐의 시작점)
                if(first) {
                    first = false;
                    q.push({i / 5, i % 5});
                    visit[i / 5][i % 5] = true;
                }
            }
        }
        
        // 첫 학생은 큐에 들어갔으므로 cnt는 1부터 시작
        int cnt = 1;
        while(!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            
            // 모든 조건을 만족하고 학생이 7명이면 true 리턴
            if(cnt == 7) return true;
            
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 범위를 벗어나는 경우 continue
                if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
                // 전에 방문했거나, 선택된 학생이 아니라면 continue; 
                if(visit[nx][ny] || !checked[nx][ny]) continue;
                q.push({nx, ny});
                visit[nx][ny] = true;
                cnt++;
            }
        }
        
        // 위의 조건에 하나라도 위반되면 큐가 전부 pop되고 난 후 
        // while문을 빠져나왔을 때, 7명이 안되므로 false를 리턴
        return false;
    }
    
    // DFS : 25명의 학생 중 7명을 선택하는 조합 
    void DFS(int idx, int cnt) {
        if(cnt == 7) {
            if(isMoreThanFour() && isAdjacent()) answer++;
            return;
        } else {
            for(int i = idx; i < 25; i++) {
                if(!pick[i]) {
                    pick[i] = true;
                    DFS(i, cnt + 1);
                    pick[i] = false;
                }
            }
        }
    }
    
    int main(void) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                cin>>map[i][j];
            }
        }
        
        DFS(0, 0); // 인덱스 번호, 선택된 학생 수
        cout<<answer;
    }

    댓글

Designed by Tistory.