백준 1941 - 소문난 칠공주(복습)

문제 링크입니다 https://www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

DFS에 익숙하지는 않아 https://yabmoons.tistory.com/117 님의 접근 방식을 참고했습니다.

 

DFS, BFS를 모두 사용한 문제입니다

 

1번 기능을 구현하는 함수, 3번과 4번을 구현하는 함수와 2번 기능을 구현하는 함수로 나누어서 풀었습니다.

 

접근방법 

1. DFS를 통해 7명의 학생을 뽑습니다. (1,2,3,4,5,6,7)이나 (7,6,5,4,3,2,1)은 똑같기에 1번부터 차례대로 선택합니다.

2. 7명의 학생 중에서 임도연파의 학생이 3명 이하인지 찾습니다.

3. 3명 이하라면 학생들이 상, 하, 좌, 우에 인접해 있는지 찾습니다.

 

저는 이차원 배열에 저장되는 학생들을 일차원 배열에 정보롤 저장한 뒤에 다시 이차원 배열로 옮겼습니다.

 

접근 방법 - 1번

void dfs(int x, int y) {
    if (y == 7) {
        if (cnt_Y()) {
            if (find_people()) {
                can++;
            }
        }
        return;
    }
    else {
        for (int i = x; i < 25; i++) {
            if (!Select[i]) {
                Select[i] = true;
                dfs(i, y + 1);
                Select[i] = false;
            }
        }
    }
}

선택한 학생이 7명 미만일 경우에 선택되지 않았던 학생들을 선택합니다. 다음 학생일때에도 선택이 되어야하기에 실행은 한뒤에 선택을 해제하는 것이 중요합니다.

 

 

접근 방법 2번

bool cnt_Y() {
    int cnt = 0;
    for (int i = 0; i < 25; i++) {
        if (Select[i]) {
            if (people[i / 5][i % 5] == 'Y') cnt++;
        }
    }
    if (cnt > 3) {
        return false;
    }
    return true;
}

선택된 학생들이 Y라면 cnt를 증가시켰으며 3보다 클 경우 다시 DFS를 돌렸습니다. 

 

 

접근 방법 3번

    - bool check[6][6], bool q_check[6][6] 이 두배열을 이용했습니다. check 배열은 선택된 학생들의 위치를 알려줍니다.

      q_check 배열은 해당 칸의 학생이 선택 되었었는지를 저장합니다. 이를 이용해서 BFS를 돌렸습니다.

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

char people[5][5];
bool Select[25];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int can;

bool cnt_Y() {
    int cnt = 0;
    for (int i = 0; i < 25; i++) {
        if (Select[i]) {
            if (people[i / 5][i % 5] == 'Y') cnt++;
        }
    }
    if (cnt > 3) {
        return false;
    }
    return true;
}

bool find_people() {
    queue<pair<int, int>> q;
    bool check[6][6];
    bool q_check[6][6];
    memset(check, false, sizeof(check));
    memset(q_check, false, sizeof(q_check));
    int first = 0;
    for (int i = 0; i < 25; i++) {
        if (Select[i]) {
            check[i / 5][i % 5] = true;
            if (first == 0) {
                first++;
                q_check[i / 5][i % 5] = true;
                q.push(make_pair(i / 5, i % 5));
            }
        }
    }
    int cnt = 1;
    int can_make = 0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (cnt == 7) {
            can_make = 1;
            break;
        }
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && yy >= 0 && xx < 5 && yy < 5) {
                if (check[xx][yy] && !q_check[xx][yy]) {
                    q_check[xx][yy] = true;
                    q.push(make_pair(xx, yy));
                    cnt++;
                }
            }
        }
    }
    if(can_make == 1) return true;
    return false;
}

void dfs(int x, int y) {
    if (y == 7) {
        if (cnt_Y()) {
            if (find_people()) {
                can++;
            }
        }
        return;
    }
    else {
        for (int i = x; i < 25; i++) {
            if (!Select[i]) {
                Select[i] = true;
                dfs(i, y + 1);
                Select[i] = false;
            }
        }
    }
}

void solve() {
    dfs(0, 0);
    cout << can;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> people[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!