백준 / 2422번 / 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 / C++

#출처 : https://www.acmicpc.net/problem/2422

이 문제는 두가지의 풀이를 적어두고 싶다. 첫번째로 나는 chk 배열을 [N의 개수][N의 개수] 크기로 2차원 배열로 잡고 for문을 돌며

ans 값을 증가시켜 최종적으로 출력하는 방법을 택했고, 친구는 DFS를 이용해서 풀었다.

DFS 를 이용한 풀이에 익숙해지고자 두 풀이 모두 적어두려한다.

#풀이(단순 for문 이용)

#include <iostream>
#define endl '\n'
using namespace std;
 
int N, M;
bool chk[205][205];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        int p, q;
        cin >> p >> q;
        chk[p][q] = chk[q][p] = true;
    }
    int ans = 0;
    for (int i = 1; i <= N; ++i)
        for (int j = i + 1; j <= N; ++j)
        {
            if (chk[i][j]) continue;
            for (int k = j + 1; k <= N; ++k)
            {
                if (chk[i][k] || chk[j][k]) continue;
                ++ans;
            }
        }
    cout << ans << endl;
    return 0;
}

#풀이(DFS 이용)

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;
 
int N, M, set[5], cnt;
vector<int> no[205];
 
void DFS(int x, int depth)
{
    if (depth == 4)
    {
        for (int i = 1; i <= 3; ++i)
        {
            for (auto num : no[set[i]])
            {
                if (i == 1)
                {
                    if (num == set[2] || num == set[3]) return;
                }
                else if (i == 2)
                {
                    if (num == set[1] || num == set[3]) return;
                }
                else if (i == 3)
                {
                    if (num == set[1] || num == set[2]) return;
                }
            }
        }
        ++cnt;
        return;
    }
 
    for (int i = x; i <= N; ++i)
    {
        set[depth] = i;
        DFS(i + 1, depth + 1);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        int p, q;
        cin >> p >> q;
        no[p].push_back(q);
    }
    DFS(1, 1);
    cout << cnt << endl;
    return 0;
}