[백준] 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 JavaScript

혅·2024년 6월 26일

백준, 프로그래머스 -JavaScript-

목록 보기

61/215

문제

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

입력

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

출력

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

예제 입력

5 3
1 2
3 4
1 3

예제 출력

내가 했던 풀이 방법

(N+1)×(N+1) 크기의 dont 배열을 선언하고, false로 채워준다. dont 배열은 섞으면 안 되는 아이스크림의 조합을 나타내며 섞으면 안 되는 경우 true 값을 가진다.
input을 순회하여 불가능한 조합에 true를 저장해준다. 예를 들어 1번 아이스크림과 2번 아이스크림을 조합하면 안 되는 경우, dont[1][2]와 dont[2][1]에 true를 저장해준다.
아이스크림 조합을 저장할 Set을 선언해준다.
빈 배열을 iceCream으로 가지고, prev를 0으로 가지는 DFS를 호출한다. DFS에서는 iceCream 배열의 length가 3인 경우, iceCream 조합을 문자열로 변환하여 set에 저장해주고 return 한다. length가 3이 안 된 경우, prev+1부터 N까지 아이스크림을 이용해 조합을 만들어준다. isPossible 변수를 true로 초기화해주고, iceCream 배열을 순회하여 조합할 예정인 아이스크림 번호와 현재 iceCream에 담긴 아이스크림 전부 검사했을 때 조합 하면 안 되는 아이스크림이 있다면 isPossible을 false로 바꿔준다. isPossible이 최종적으로 true일 경우, DFS에 iceCream 배열에 i를 추가한 배열과 i를 prev로 하여 재귀 호출시켜준다.
DFS 호출이 끝난 뒤 set의 담긴 조합의 갯수를 출력해준다.

코드

const fs = require('fs');
let [n, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(n.trim().split(' ')[0]);
let M = Number(n.trim().split(' ')[1]);

let dont = Array.from({ length: N + 1 }, () => Array(N + 1).fill(false));

for (let i = 0; i < M; i++) {
  let [a, b] = input[i].trim().split(' ').map(Number);
  dont[a][b] = true;
  dont[b][a] = true;
}

let set = new Set();
function DFS(iceCream, prev) {
  if (iceCream.length === 3) {
    set.add(iceCream.join(' '));
    return;
  }

  for (let i = prev + 1; i <= N; i++) {
    let isPossible = true;
    for (let j = 0; j < iceCream.length; j++) {
      if (dont[iceCream[j]][i]) {
        isPossible = false;
        break;
      }
    }
    if (isPossible) {
      DFS([...iceCream, i], i);
    }
  }
}

DFS([], 0);
console.log(set.size);