문제

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다. baekjoon

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_valid(vector<int> graph[], int a, int b, int c) {
  for (int connected : graph[a]) {
    if (connected == b || connected == c) return false;
  }

  for (int connected : graph[b]) {
    if (connected == a || connected == c) return false;
  }

  for (int connected : graph[c]) {
    if (connected == b || connected == a) return false;
  }

  return true;
} 

int main() {
  int n, m;
  cin >> n >> m;
  
  vector<int> ind;
  for (int i = 0; i < n - 3; i++) ind.push_back(0);
  for (int i = 0; i < 3; i++) ind.push_back(1);

  vector<int> graph[n + 1];
  while (m--) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  int result = 0;
  do {
    vector<int> selected;
    for (int i = 0; i < n; i++) {
      if (ind[i] == 1) selected.push_back(i + 1);
    }

    if (is_valid(graph, selected[0], selected[1], selected[2])) result++;
  } while (next_permutation(ind.begin(), ind.end()));

  cout << result;
}

풀이

안맞는 것들을 인접 리스트로 보관한다. 아이스크림 3개 선택에 대해 조합을 만든 후, is_valid 함수 내에서 만든 인접 리스트를 토대로 유효한 조합이 될 수 있는지를 체크한다.