[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;
}