[프로그래머스/C++] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP)

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 그래프의 모양을 파악하는 문제다.

 

자세히 보면 막대그래프는 순환하지 않고, 8자 그래프는 나가는 간선이 2개가 있는 특이점을 발견할 수 있다.

이를 활용하면 그래프의 모양이 어떤 모양인지 쉽게 파악할 수 있다.

 

그래프를 돌면서 만약 간선이 2개인 점이 나오면 그 그래프는 8자 그래프, 나가는 간선이 없으면 막대 그래프,

만약 다시 시작했던 노드로 돌아오면 도넛 그래프다.

 

생점의 특이사항은 들어오는 간선이 하나도 없다는게 특징이다.

문제는 막대그래프의 끝점에서도 이러한 특징이 나타날 수 있는데, 제한사항에 보면 적어도 두개의 그래프를 생점에서는 생성하므로, 나가는 간선의 길이가 2보다 크거나 같으면서 들어오는 간선이 없으면 생점이다. 

 

[아이디어 정리]

1. 나가는 간선이 2이상 들어오는 간선이 없으면 생점이다.
2. 생점을 기준으로 그래프 탐색을 시작한다.
3. 그래프 탐색 도중에 나가는 간선이 2개인 노드가 발견되면 8자 그래프, 나가는 간선이 없다면 막대 그래프, 시작 노드로 돌아왔다면 도넛 그래프다.

 

Code

 

 

 

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<vector<int>> outN(1000001); //out
vector<vector<int>> inN(1000001); //int
set<int> nodeSet;

int calc(int stN)
{
    int nowN=stN;
    while(true)
    {
        if (outN[nowN].size()>=2){
            return 3;
        }
        else if (outN[nowN].size()==0)
        {
            return 2;
        }
        nowN=outN[nowN][0];        
        if (nowN==stN)
        {
            return 1;
        }
    }
}


vector<int> solution(vector<vector<int>> edges) {
    int maxNum=0;
    vector<int> answer(4,0);
    for (int i=0; i<edges.size(); i++)
    {
        outN[edges[i][0]].push_back(edges[i][1]);
        inN[edges[i][1]].push_back(edges[i][0]);
        nodeSet.insert(edges[i][1]);
        nodeSet.insert(edges[i][0]);
    }
    int stN;
    for (set<int>::iterator i=nodeSet.begin(); i!=nodeSet.end(); i++)
    {
        if (inN[*i].size()==0 && outN[*i].size()>=2)
        {
            stN=*i;
            break;
        }
    }
    answer[0]=stN;
    for (int i=0; i<outN[stN].size(); i++)
    {
        answer[calc(outN[stN][i])]+=1;
    }  
    return answer;
}

 

 

Code2

 

 

 

#include <string>
#include <vector>
#include <set>
using namespace std;

int tt[1000001]; //out
int tt2[1000001]; //int
vector<int> solution(vector<vector<int>> edges) {
    int maxNum=0;
    vector<int> answer(4,0);
    for (int i=0; i<edges.size(); i++){
        tt[edges[i][0]]+=1;
        tt2[edges[i][1]]+=1;
        if (maxNum<edges[i][0])
        {
            maxNum=edges[i][0];
        }
        if (maxNum<edges[i][1])
        {
            maxNum=edges[i][1];
        }
    }
    // 도 막 8
    int stN;
    for (int i=1; i<=maxNum; i++)
    {
        if (tt[i]>=2)
        {
            answer[3]+=1;
            if (tt2[i]==0)
            {
                stN=i;
                answer[3]-=1;
            }
        }
        if (tt2[i]>=1)
        {
            if(tt[i]==0)
            {
                answer[2]+=1;
            }
        }
    }
    answer[0]=stN;
    answer[1]=tt[stN]-answer[2]-answer[3];
    return answer;
}

 

 

---

 

아래 있는 풀이는 정점에 써진 가장 큰 숫자와 개수가 같다고 해도 풀려서 이를 이용한 풀이다..

처음에 풀었을 때 분명 같은 방법으로 풀었는데 테스트 케이스에서 틀리다고 나왔다...

너무 화가나서 다시 문제를 풀었더니 같은 방법인데 또 풀렸다... 분명 뭔가 달라서 틀렸을텐데 다시 봐도 똑같아 보였다

알고보니 생점을 구할 때, 나가는 간선이 2개 이상이라는 조건을 빼먹어서 틀린거였다;;;

내 시간 돌려줘!

 

프로그래머스