문제

강토는 Day Of Mourning의 기타리스트로, 다가오는 공연을 준비하고 있다.

어느 날 강토의 집에 도둑이 들어서 기타를 모두 도둑맞고 말았다. 기타를 사야 한다.

강토는 공연 때 연주할 노래의 목록을 뽑아 놓았다. 하지만, 하나의 기타로 모든 곡을 연주할 수는 없다. 어떤 기타는 어떤 곡을 연주할 때, 이상한 소리가 나기 때문이다. 항상 완벽을 추구하는 강토는 이런 일을 용납하지 않는다.

최대한 많은 곡을 제대로 연주하려고 할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오.

예를 들어, GIBSON으로 1, 2, 3번 곡을 제대로 연주할 수 있고, FENDER로 1, 2, 5번 곡을 제대로 연주할 수 있고, EPIPHONE으로 4, 5번 곡을 제대로 연주할 수 있고, ESP로 1번곡을 제대로 연주할 수 있다면, 세준이는 EPIPHONE과 GIBSON을 사면 최소의 개수로 모든 곡을 연주할 수 있다.

입력

첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 정보가 1번 곡부터 차례대로 주어진다. Y는 연주할 수 있는 것이고, N은 없는 것이다. 기타의 이름은 알파벳 대문자로만 이루어져 있고, 길이는 2 이상, 50 이하이다. 두 기타의 이름이 같은 경우는 없다.

출력

첫째 줄에 필요한 기타의 개수를 출력한다. 만약 연주할 수 있는 곡이 없으면 -1을 출력한다.

예제 입력

4 5
GIBSON YYYNN
FENDER YYNNY
EPIPHONE NNNYY
ESP YNNNN

예제 출력

2

내가 했던 풀이 방법

1. info(기타 정보)에 대해서 기타의 이름을 사용하지 않으므로 기타가 연주할 수 있는 곡 정보만 남겨준다.
2. minGuitar를 Infinity로 maxSong을 0으로 초기화해준다. 여기서 minGuitar는 문제에서 요구하는 정답인 필요한 최소의 기타 개수이고 maxSong은 최대로 연주할 수 있는 노래 수이다. 문제에서 모든 곡을 다 연주하는 것이 아닌 최대한 많은 곡을 연주하는 것이기 때문에 필요하다.
3. DFS에서 guitar와 song은 모두 set이고 사용한 기타와 현재 연주할 수 있는 곡의 번호가 담겨있다. current는 이번에 체크할 기타 번호가 된다. 즉, current가 1일 경우 1번 기타(예시 입력 기준 FENDER)를 체크한다고 보면 된다.
4. song.size가 maxSong보다 클 경우, maxSong을 song.size로 갱신해주고 minGuitar를 guitar.size로 저장해준다. 최대한 많은 노래를 해야하기 때문에 무조건 maxSong이 갱신될 경우, minGuitar로 갱신되어야 한다. 만약 songCount가 maxSong과 같은 경우에는 minGuitar와 현재 guitar.size 중 최소값으로 갱신한다.
5. current가 N이 되면 모든 기타에 대해서 체크한 것이므로 return 한다.
6. 해당 기타를 사용하느냐 안 하느냐만 선택하면 되기 때문에 2번에 DFS를 호출한다. 기타를 사용하지 않을 경우, guitar와 song에는 영향이 없으므로 기존 set을 그대로 전달하고 current만 1 증가시켜 다음 기타를 검사하게 한다. 기타를 사용할 경우, 해당 기타를 guitar에 추가하고 기타로 연주할 수 있는 곡을 갱신해줘야 하기 때문에 해당 기타가 연주할 수 있는 곡을 song에 추가해준다. 이를 DFS에 매개변수에 넣어준다.
7. 모든 DFS가 끝난 뒤에 minGuitar에는 최대한 많은 곡을 연주하면서 사용할 수 있는 최소의 기타가 minGuitar에 들어간다. 만약 maxSong이 0일 경우에는 모든 곡이 연주되지 못한다는 것이므로 -1을 출력한다.

코드

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

let [N, M] = n.trim().split(' ').map(Number);
info = info.map((i) => i.trim().split(' ')[1].split(''));

let minGuitar = Infinity;
let maxSong = 0;

function DFS(guitar, song, current) {
  let songCount = song.size;

  if (songCount > maxSong) {
    maxSong = songCount;
    minGuitar = guitar.size;
  } else if (songCount === maxSong) {
    minGuitar = Math.min(minGuitar, guitar.size);
  }

  if (current === N) return;

  DFS(guitar, song, current + 1);

  let newGuitar = new Set(guitar);
  let newSong = new Set(song);
  newGuitar.add(current);

  for (let j = 0; j < M; j++) {
    if (info[current][j] === 'Y') {
      newSong.add(j);
    }
  }

  DFS(newGuitar, newSong, current + 1);
}

DFS(new Set(), new Set(), 0);

console.log(maxSong === 0 ? -1 : minGuitar);

회고

최근 풀었던 DFS 문제 중에 제일 오래 걸렸던 문제... 모든 곡을 다 연주하면서 최소 기타 수를 물어볼 줄 알았는데 최대한 많은 곡이라는 조건이 있어서 더 복잡해졌던 것 같다. 문제를 꼭 제대로 읽어야 한다는 걸 다시 한 번 상기하게 해준 문제... 찬찬히 생각하면 코드도 간단한데 너무 전형적인 DFS로 접근한 것 같다.