[알고리즘 연습] 프로그래머스 도넛과 막대 그래프 (LEVEL 2, 자바스크립트)

문제

프로그래머스

---

풀이

생성한 노드, 도넛 모양 그래프 개수, 막대 모양 그래프 개수, 8자 모양 그래프 개수를 구하기 위해 이들을 각각 구분할 수 있는 수단이 필요했다. 그 수단은 바로 각 노드에서 들어오는 간선(in)의 개수와 나가는 간선(out)의 개수였다.

• 생성한 노드: in === 0 out >=2, out이 2개 이상인 이유는 모든 그래프 개수의 합은 2이상이고 생성한 노드는 모든 그래프와 연결되어 있다.
• 막대 모양 그래프: out === 0, out이 0인 노드는 막대 모양 그래프의 최상단 노드 밖에 없다.
• 8자 모양 그래프: in >= 2 out >=2, 8자 모양 그래프의 중앙에 위치한 노드의 특징이다.
• 도넛 모양 그래프: 생성한 생성의 out개수 - (막대 모양 개수 + 8자 모양 개수), 별도의 특징이 없어 생성한 노드는 모든 그래프와 연결되어 있는 특징을 이용한다.

이 문제를 보면 그래프 탐색을 통해 정답을 구해야될거 같았지만 규칙을 찾아서 쉽게 정답을 구할 수 있었다. 앞으로 그래프 문제가 나오면 바로 그래프 탐색을 시도하기보단 더 나은 방법이 있는지 고민해보는 자세를 가져야겠다. 

소스 코드  

function solution(edges) {
  const answer = Array(4).fill(0);
  const counter = edges.reduce((res, edge) => {
    const [a, b] = edge;
    
    if (!res[a]) {
      res[a] = [0, 1];
    } else {
      res[a][1] += 1;
    }
    
    if (!res[b]) {
      res[b] = [1, 0];
    } else {
      res[b][0] += 1;
    }
      
    return res;
  }, {}); // [in, out]
    
  // 생성한 정점: in === 0 && out >= 2
  // 막대 모양: out === 0
  // 8자 모양: in >= 2 && out >= 2
  // 도넛 모양: 생성한 생성의 out개수 - (막대 모양 개수 + 8자 모양 개수)
  for(const node in counter) {
    const [i, o] = counter[node];
      
    if (i === 0 && o >= 2) {
      answer[0] = +node;
    } 
    if (o === 0) {
      answer[2] += 1;
    }
    if (i >= 2 && o >= 2) {
      answer[3] += 1;
    }
  }
  answer[1] = counter[answer[0]][1] - (answer[2] + answer[3]);
  
  return answer;
}