[C++] 프로그래머스 : 도넛과 막대그래프

처음에 이 문제를 보고 어떤식으로 풀어야 할 지 막막해서 예시를 보면서 생각 정리를 해보았다.

이 그림을 보면 일단 2라는 점이 생성한 정점이고 2번이 가리키는 1번은 도넛 모양 그래프, 그 다음 3번은 막대 모양 그래프이다.

1. 먼저 생성한 정점을 찾는다.
   • 그래프의 수는 2이상이므로 가리키는 점은 2개 이상이면서 자신을 안가리키고 있는 정점 찾기
2. 생성한 점이 가리키는 점을 순회하면서 무슨 그래프인지 찾는다.

• 도넛 모양 그래프 : 정점들을 방문하다보면 원래 출발했던 정점으로 돌아온다.
• 막대 모양 그래프 : 정점들을 방문하다보면 아무것도 가리키지 않는 정점이 있다.
• 8자 모양 그래프 : 정점들을 방문하다보면 중간에 두 개의 정점을 가리키는 정점이 있다.

이러한 생각으로 코드를 짰다.

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int created = 0, donut = 0, bar = 0, eight = 0, init;
vector<vector<int>> v(1000001);
vector<int> answer;

void graph(int n) {
  //막대 모양 그래프
  if (v[n].empty()) {
      bar += 1;
      return;
  }
  //8자 모양 그래프
  if (v[n].size() == 2) {
      eight += 1;
      return;
  }
  //도넛 모양 그래프
  if (v[n][0] == init) {
      donut += 1;
      return;
  }
  //아직 확정되지 않았으면 계속해서 탐색
  graph(v[n][0]);
}

vector<int> solution(vector<vector<int>> edges) {
  vector<bool> BOOL(1000001, false);
  unordered_set<int> nodes;

  for (int i = 0; i < edges.size(); i++) {
      v[edges[i][0]].push_back(edges[i][1]);
      BOOL[edges[i][1]] = true;
      nodes.insert(edges[i][0]);
      nodes.insert(edges[i][1]);
  }

  //생성한 정점 찾기
  for (int node : nodes) {
      if (!BOOL[node] && v[node].size() >= 2) {
          created = node;
          break;
      }
  }

  //어떤 그래프인지 확인
  for (int i = 0; i < v[created].size(); i++) {
      init = v[created][i];
      graph(v[created][i]);
  }

  answer = {created, donut, bar, eight};
  return answer;
}

int main(void) {
  vector<vector<int>> edges = {{4, 11}, {1, 12}, {8, 3}, {12, 7}, {4, 2}, {7, 11}, {4, 8}, {9, 6}, {10, 11}, {6, 10}, {3, 5}, {11, 1}, {5, 3}, {11, 9}, {3, 8}};
  vector<int> result = solution(edges);
  for (int i = 0; i < 4; i++) {
      cout << result[i] << " ";
  }
  cout << endl;
  return 0;
}

처음에 nodes를 vector로 하였더니 nodes에 값을 넣을때 값이 들어가 있는지 없는지 비교를 해줬어야해서 시간초과가 났었다. 그래서 조금의 도움을 빌려서 unordered_set을 사용하였더니 시간초과 없이 풀었다. 자료구조 공부를 해야겠다...