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

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

 

문제 분석

아래와 같이 도넛모양, 막대모양, 8자모양 그래프가 있다.

여기서 문제의 핵심은 “이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결”했다는 부분이다.

즉 아래와 같이 정점을 찾으면 거기에 연결된 것은 도넛, 막대, 8자그래프 중 하나여야 한다는 소리이다.

그렇기에 정점에 아래와 같이 도넛그래프 2개를 합친 것 같은 모양이 붙어있거나 하는 일은 없다. (나는 괜히 이 경우를 생각하면서 어렵게 생각했었다.)

여기까지 이해하면 문제는 많이 단순해진다. 먼저 정점을 찾고, 각 부분에 연결된 그래프들이 어떤 모양(도넛, 막대, 8자)인지 판별해내면 된다.

아이디어

앞서 살펴봤듯이 문제는 크게 두 부분으로 나뉜다.

1. 정점 찾기
2. 각 부분에 연결된 그래프 모양 판별하기

정점 찾기

먼저 정점의 조건은 아래와 같다.

1. 들어오는 간선은 없고, 나가는 간선만 있다.
2. 들어오는 간선의 개수가 0인것이 여러개라면 그중 나가는 간선의 수가 가장 큰 것이 정점이다.

1번 조건은 “이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.” 라는 구절에서 유추할 수 있다. 만약 정점으로 들어오는 간선이 있다면 문제에서 주어진 조건에 맞지 않다.

만약 아래와 같이 그래프가 생겼다고 가정해보자.(1번 예시에 7번이 추가된 모습)

원래 이 그래프의 정점은 2번인데, 문제에서 도넛, 막대, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선을 연결했다는 말과 맞지 않는 것을 확인할 수 있다. 그래서 정점은 들어오는 간선이 없어야 한다.

2번 조건을 이해하기 위해 1번 예시를 다시 보도록 하자. 우리는 2번 정점과 4번 정점 모두 들어오는 간선이 0개이지만 직관적으로 2번 정점이 우리가 찾는 정점임을 알 수 있다. 이것도 같은 구절을 통해 알 수 있다. 문제를 보면 “그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.”라고 했다.

즉 우리가 찾는 정점은 모든 그래프들과 연결되어 있기 때문에 나가는 정점의 개수가 가장 많은 정점이다.

각 부분에 연결된 그래프 모양 판별하기

각 그래프의 모양을 관찰하면 그래프의 모양을 어떻게 판별할지 알 수 있다.

먼저 막대모양 그래프는 쭉 따라가다보면 나가는 간선이 없는 정점이 나오는 그래프이다. 문제는 도넛이랑 8자 모양을 어떻게 구별하느냐이다. 둘 다 쭉 따라가다보면 자기 자신이 나오기 때문이다.

하지만 8자 모양 그래프에는 도넛 모양 그래프와 달리 나가는 간선이 2개인 정점이 있다. 이것을 이용해 도넛과 8자 그래프를 구분할 수 있다.

🔑그래프 구분

막대 모양 그래프 : 순회하다 보면 나가는 간선이 1개인 정점을 만난다.
8자 모양 그래프 : 순회하다 보면 나가는 간선이 2개인 정점을 만난다.
도넛 모양 그래프 : 순회하다 보면 자기 자신을 만나게 된다.

그래서 코드에는 나가는 간선이 1개, 2개인 정점을 만나면 순회를 멈추고, 만약 순회를 끝까지 하게 되어 방문한 적이 있는 정점을 만나게 된다면 도넛 모양 그래프로 판단할 것이다.

코드

전체 코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <queue>
using namespace std;

bool isExist[1000005];
int indegrees[1000005];
int outdegrees[1000005];
vector<int> vec[1000005];

bool visited[1000005];

int doughnut,stick,eight;

void bfs(int start){
    queue<int> q;
    visited[start]=true;
    
    q.push(start);
    bool flag=true;
    while(!q.empty()&&flag){
        int curVertex=q.front();
        q.pop();
        
        //나가는 간선이 0개인 정점 : 막대 모양 그래프
        if(outdegrees[curVertex]==0){
            stick++;
            return;
        }
        
        //나가는 간선이 2개인 정점 : 8자 모양 그래프
        if(outdegrees[curVertex]==2){
            eight++;
            return;
        }
        
        for(int i=0;i<vec[curVertex].size();i++){
            int nxtVertex=vec[curVertex][i];
            //이미 방문한 적이 있는 정점 : 도넛 모양 그래프
            if(visited[nxtVertex]){
                flag=false;
                break;
            }
            visited[nxtVertex]=true;
            q.push(nxtVertex);
        }
    }
    doughnut++;
    return;
}

vector<int> solution(vector<vector<int>> edges) {
    vector<int> answer;
    for(auto k:edges){
        isExist[k[0]]=true;
        isExist[k[1]]=true;
        
        outdegrees[k[0]]++;
        indegrees[k[1]]++;
        vec[k[0]].push_back(k[1]);
    }
    
    //정점 찾기(들어오는 간선이 없고 나가는 간선이 많은)
    priority_queue <pair<int,int>> cand;
    for(int i=1;i<1000005;i++){
        if(!isExist[i])continue;
        if(indegrees[i]==0)cand.push({outdegrees[i],i}); // 나가는 간선 개수, 정점번호
    }
    
    //들어오는 간선이 없는 정점들을 나가는 간선 개수로 정렬한 뒤 가장 위의 정점을 가져옴 : 메인 정점
    int mainVertex = cand.top().second;
    
    //메인 정점에 연결된 정점들을 하나씩 잡아 bfs를 통한 순회
    for(int i=0;i<vec[mainVertex].size();i++){
        int tmpVertex=vec[mainVertex][i];
        bfs(tmpVertex);
    }
    
    answer.push_back(mainVertex);
    answer.push_back(doughnut);
    answer.push_back(stick);
    answer.push_back(eight);
    
    return answer;
}

 

실수했던 부분

나는 마지막 테스트케이스인 35번 테스트케이스만 통과를 못했었는데 그 이유는 처음에 정점 찾기 부분을 아래와 같이 짰기 때문이다.

    //정점 찾기(들어오는 간선이 없고 나가는 간선이 많은)
    priority_queue <pair<int,int>> cand;
    for(int i=1;i<1000005;i++){
        if(!isExist[i])break; //실수한 부분, 이후 continue로 바꾸어 성공
        if(indegrees[i]==0)cand.push({outdegrees[i],i}); // 나가는 간선 개수, 정점번호
    }

내 마음대로 정점의 번호가 순서대로 부여된다고 생각했는데 문제의 제한 사항을 보면 그런 말은 없다. 즉 1 3 5 7번 정점이 존재할 수 있다는 말이다. 그런데 위와 같이 break문을 걸면 1번 정점만 간선의 개수를 체크하기 때문에 segmentation fault (core dumped)가 발생한다.

또 처음에 짰을 때는 아래 bfs를 순회할 때 새로운 정점에서 순회를 시작할 때 마다 visited배열을 초기화 했었다. 그런데 생각해보니 각 정점은 하나의 그래프들과 연결된다. 그렇기에 그래프간에 정점을 공유하지 않아 visited배열을 계속 초기화할 필요가 없다.

    //메인 정점에 연결된 정점들을 하나씩 잡아 bfs를 통한 순회
    for(int i=0;i<vec[mainVertex].size();i++){
		    fill(&visited[0],&visited[0]+1000005,false); //정답 코드에선 빠진 부분
        int tmpVertex=vec[mainVertex][i];
        bfs(tmpVertex);
    }