programmers 258711 - 도넛과 막대 그래프

요구사항

• 세 타입의 그래프
  • 도넛 모양 그래프
    

    

  • 막대 모양 그래프
    

    

  • 8자 모양 그래프
    

    

• 단방향 간선
• 크기가 n인 도넛의 모양 그래프는 n개의 정점과 n개의 간선이 존재

구하려는 것

세 타입의 그래프 여러 개가 있고, 그와 무관한 정점을 하나 그린 뒤, 각 그래프의 임의의 정점 하나로 향하는 간선들을 연결했다.

간선 정보가 주어지면 [생성한 정점의 번호, (정점 생성 전) 도넛그래프 수, 막대 그래프 수, 8자 그래프 수]를 담은 1차원 배열을 return

입력

[[2, 3], [4, 3], [1, 1], [2, 1]]

출력

[2, 1, 1, 0]

문제 첫인상

• 도넛이 세가지 있구나
• 깊이 우선으로 탐색해보자
• 생성한 정점은 어떻게 계산할 수 있을까
• 막대 그래프는 루프가 없는 경우로 판별하면 되겠다
• 도넛 그래프는 루프가 하나 있는 경우로 판별하면 되겠다
• 8자 그래프는 루프가 2개 있는 경우로 판별하면 되겠다
• 정점은 나가는 간선만 존재하는 정점으로 판별하면 될 듯?

pseudo code

1. input으로 그래프에 값 넣기
2. function makeGraph(input){ const graph = new Map(); // for 문으로 input 돌면서 값 넣기 }
3. 생성한 정점 계산하기
4. function findNew(graph){ // graph를 순회하면서 바깥으로 향하는 정점의 개수가 가장 많은 것을 생성한 정점으로. }
5. dfs 구현아 어려워
6. const route = []; const visited = []; while(stack){ const now = stack.pop(); // 탐색 알고리즘 생각 for(node in graph[now]){ stack.push(node); } route.push(now); visited.push(now); }
7. stack에 8-3-5-3-8 로 탐색안되고 8-3-8-5로 가버림 이거 어떻게 걸러야될까
   1. visited = [4,8]
   2. visited = [4,8,3] // 3->5,8
   3. visited에 있는 경우 거르면 visited = [4,8,3,5] 가능
   4. 근데 나중에 8을 다시 넣으려고 할 때 3에서 걸림
      1. 두개 있을 때는 visited 안한거 넣어주고
      2. 한개 있을 때는 그냥 넣어주면 안되나..

// 다음에 추가할 후보가 이미 방문한 경우
if(visited.includes(next)){
    thereIs = true;
}
// 이미 방문한 후보가 있고, 추가할 노드가 2개 이상인 경우
if(thereIs && graph.get(now).length > 2){
    // 이미 방문한 적 없는 노드를 먼저 추가 -> 아 배열에 추가하고 붙일까

    // 방문한 적 있으면 already에 push  
    if(visited.includes(next)){  
    already.push(next)  
    }else{  
    // 방문한 적 없으면 yet  
    yet.push(next)  
    }  
    // already + yet 형태로 푸쉬  
    stack.push(already.extend(yet));

내 아이디어에서의 한계점

function makeGraph(arr) {
  const graph = new Map();
  for ([node, edge] of arr) {
    if (!graph.has(node)) {
      graph.set(node, []);
    }
    graph.get(node).push(Number(edge));
  }
  return graph;
}


function findNew(graph) {
  // 들어오는 방향의 간선이 없는 정점 찾기
  let maxNumNode = [-Infinity, -Infinity];
  for ([node, value] of graph) {
    if (value.length >= maxNumNode[1]) {
      maxNumNode[0] = node;
      maxNumNode[1] = value.length;
    }
  }

  return maxNumNode[0];
}

function main(input) {
  const graph = makeGraph(input);
  const newNode = findNew(graph);
  // [newNode, 도넛, 막대, 8자]
  const answer = [newNode, 0, 0, 0];

  // dfs관련
  const stack = [newNode];
  const visited = [];
  const route = [];
  let loop = [0, 0];

  while (stack.length > 0) {
    const now = stack.pop();
    const already = [];
    const notYet = [];

    if (graph.has(now)) {
      for (node of graph.get(now)) {
        if (visited.includes(node)) {
          already.push(node);
        } else {
          notYet.push(node);
        }
      }
      route.push(now);

      stack.push(...already.concat(notYet));

      const value = graph.get(now);
      value.splice(value.indexOf(now), 1);
    } else {
      answer[2] += 1;
      route.push(now);
    }

    // 루프 계산이 위태위태
    if (visited.includes(now)) {
      loop[1] += 1;
      if (loop[1] === 1) {
        answer[1] += 1;
      } else if (loop[1] === 3) {
        answer[1] -= 1;
        answer[3] += 1;
        loop = [0, 0];
      }
    }

    visited.push(now);
  }
  return answer;
}

나는 loop의 개수로 판별하려고 했었다.

• if문의 개수가 너무 많아서 더럽다
• loop의 개수로 판별하는 것이 뭔가 확실하지 않은 로직이었다. 도넛 그래프인지를 정확히 계산할 수 없었다.
  • 도넛 그래프로 일단 생각했다가 이미 탐색한 노드를 2번이 넘어가게 탐색하면 8자로 계산하는 것이 아이디어였는데 이 경우, 도넛 그래프로 끝날 때 loop를 초기화할 수 없게 된다.
  • 8자 그래프로 판별이 되면 도넛 그래프라고 가정하고 더했던 개수를 빼는 방식이기 때문에, 루프가 계속 도는 오류가 발생할 경우, 계속 8자 그래프로 인식할 수 있다는 것아이디어 한계 해결 고민루프 1개인 경우에 도넛그래프인지 확실하게 인식할 수 있는 경우가 필요하다.

어떤 정점이 2개 이상의 나가는 간선을 가지면 8자 그래프라는 아이디어를 이용
-> 탐색 안했던 것을 먼저 나오는 순서로 stack에 쌓아주어야 한다
-> 8자는 확실한데 도넛은 한개 나가고 한개 들어오는 것? 그것은 8자 내부에도 존재한다는 한계가 있었다.

다른 풀이를 참고해보기

이분의 아이디어는 정점이 가진 간선의 개수만으로 판별하는 것이었다.
나는 전체를 탐색하는 방식으로 생각했는데, 이분은 간선의 개수를 보고 그래프의 개수를 판별하였다.
천잰가..

1. 막대그래프 : 나가는 간선이 0개인 정점 존재 -> 그것의 개수가 막대그래프의 개수
2. 도넛그래프 : 나가는 간선 1개, 들어오는 간선 1개 -> 8자 그래프 내부에도 존재 가능함(이것만으로는 정확히 개수를 셀 수 없다)
3. 8자그래프 : 나가는 간선 2개, 들어오는 간선 2개 -> 8자 그래프 교차지점의 개수 = 8자그래프 개수
4. 생성된 정점 : 나가는 것 밖에 없는 정점 중에 간선의 개수가 가장 많은 것 = 전체 그래프 개수

생성된 정점의 간선 개수는 전체 그래프의 개수.
8자 그래프와 막대 그래프는 정확한 개수를 알 수 있다.

이게 key였다.
도넛그래프 개수 = 전체 그래프 개수 - 막대그래프 - 8자그래프
로 계산하는 천재적인 풀이...

구현

function solution(edges) {
  const graph = {};
  let maxEdges = 0;
  let stick = 0;
  let shape8 = 0;
  let doughnut = 0;
  let newNode = 0;

  // 도넛 그래프는 total-stick-shape8
  edges.forEach(([startNode, nextNode]) => {
    graph[startNode] ||= { go: 0, come: 0 };
    graph[nextNode] ||= { go: 0, come: 0 };
    graph[startNode].go++;
    graph[nextNode].come++;
  });

  Object.keys(graph).forEach((key) => {
    const item = graph[key];
    if (item.go >= 2 && item.come >= 2) {
      shape8 += 1;
    }
    if (item.go <= 0) {
      stick += 1;
    }
    if (item.come === 0) {
      if (maxEdges <= item.go) {
        newNode = key;
        maxEdges = item.go;
      }
    }
  });
  const total = maxEdges;
  doughnut = total - stick - shape8;

  const answer = [Number(newNode), doughnut, stick, shape8];

  return answer;
}

소감

복잡할수록 단순하게....
https://school.programmers.co.kr/questions/70904
이분 쩐다..