[AOJ] PICNIC

[ALGOSPOT Online Judge(AOJ)] PICNIC C++

๋ฌธ์ œ : AOJ PICNIC

๋ฌธ์ œ ์„ค๋ช…

n ๋ช…์˜ ํ•™์ƒ์ด ์ฃผ์–ด์ง€๊ณ , m ๊ฐœ์˜ ๊ฐ€๋Šฅํ•œ ์ง์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
m ๊ฐœ๋กœ ์ฃผ์–ด์ง„ ์กฐ๊ฑด์— ๋งž๊ฒŒ ์ง์„ ์ง€์„ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
๊ฐ€๋Šฅํ•˜๋‹ค๊ณ  ์ฃผ์–ด์ง€์ง€ ์•Š์€ ํ•™์ƒ๋“ค ๋ผ๋ฆฐ ์ง์ด ๋  ์ˆ˜ ์—†๊ณ , ๋ชจ๋“  ํ•™์ƒ๋“ค์€ ๊ฐ์ž์˜ ์ง์ด ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


Solution

์™„์ „ ํƒ์ƒ‰

ํ•™์ƒ์˜ ์ˆ˜๊ฐ€ ์ตœ๋Œ€ 10๋ช…์œผ๋กœ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํ™•์ธํ•˜์—ฌ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
์ตœ์•…์˜ ๊ฒฝ์šฐ ์ตœ๋Œ€ ํ•™์ƒ ์ˆ˜ 10๋ช…์ด ์ž์‹ ์„ ์ œ์™ธํ•œ 9๋ช…๊ณผ ๋ชจ๋‘ ์ง์ด ๋  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์ธ๋ฐ, ์ด ๊ฒฝ์šฐ๋Š” 9*7*5*3*1์ด๋ฏ€๋กœ ์‹œ๊ฐ„์ œํ•œ ์•ˆ์— ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
ํ•ด๋‹น ํ•™์ƒ์ด ์ง์„ ์ฐพ์•˜๋Š”์ง€์˜ ์œ ๋ฌด์ธ isFind ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ์ด ๋ฐฐ์—ด๋กœ ์žฌ๊ท€๋ฅผ ๊ณ„์† ๋Œ๋ฉฐ ๊ฒฐ๊ณผ๋ฅผ ํ™•์ธํ•ด ์ฃผ๋Š” ๋ฐฉ์‹์œผ๋กœ ํ•ด๊ฒฐํ–ˆ์Šต๋‹ˆ๋‹ค.


Description

  • ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์˜ ์ˆ˜์ธ c๊ฐ€ ์ฃผ์–ด์ง€๋ฏ€๋กœ, ์ƒˆ๋กœ์šด ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค ์ดˆ๊ธฐํ™”๋ฅผ ํ•ด์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ์˜ memset() ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค ์ดˆ๊ธฐํ™”๋ฅผ ํ–ˆ์Šต๋‹ˆ๋‹ค.

#include <iostream>
#include <cstring>
using namespace std;
bool isFriend[10][10];
bool isFind[10];
int c, n, m;
int recursion(bool isFind[10]);
int main(){
    cin >> c;
    while(c--){
        memset(isFriend,false,sizeof(isFriend));
        memset(isFind,false,sizeof(isFind));
        cin >> n >> m;
        for(int i=1;i<=m;i++){
            int st, ed;
            cin >> st >> ed;
            isFriend[st][ed] = true;
            isFriend[ed][st] = true;
        }
        int result = recursion(isFind);
        cout << result << '\n';
    }
}
int recursion(bool isFind[10]){
    int firstSearch = - 1;
    for(int i=0;i<n;i++){
        if(!isFind[i]){
            firstSearch = i;
            break;
        }
    }
    if(firstSearch== -1) return 1;
    int ret = 0;
    for(int i=firstSearch+1;  i<n; i++){
        if(!isFind[i] && isFriend[firstSearch][i]){
            isFind[firstSearch] = true;
            isFind[i] = true;
            ret += recursion(isFind);
            isFind[firstSearch] = false;
            isFind[i]=false;
        }
    }
    return ret;
}