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

[그래프-도넛과 막대 그래프]

프로그래머스

 

문제

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 존재한다. 이 그래프들과 무관한 정점을 하나 생성한 후, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선을 연결하고 각 정점에 서로 다른 번호를 매겼다.

이때 그래프의 간선 정보가 주어졌을 때, 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구하라.

 

[도넛 모양 그래프]: n개의 정점과 n개의 간선으로 이루어져 있음. 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 다시 돌아오게 됨.

도넛 모양 그래프

 

[막대 모양 그래프]: n개의 정점과 n-1개의 간선으로 이루어져 있음. 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재함

막대 모양 그래프

 

[8자 모양 그래프]: 2n+1개의 정점과 2n+2개의 간선으로 이루어져 있음. 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프 형태임

8자 모양 그래프

 

제한 사항

• 1 ≤ edges의 길이 ≤ 1,000,000
  • edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
  • 1 ≤ a, b ≤ 1,000,000
• 문제의 조건에 맞는 그래프가 주어집니다.
• 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

 

입출력 예

edges	result
[[2, 3], [4, 3], [1, 1], [2, 1]]	[2, 1, 1, 0]
[[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]]	[4, 0, 1, 2]

 

접근 방법

그래프 풀이 방법 중 하나인 DFS나 BFS로 접근하려고 했지만,, 도저히 로직이 생각나지 않아서 다른 분들의 풀이를 참고했다.

세 그래프들의 특징을 통해 [들어오는 간선의 개수, 나가는 간선의 개수]로 접근하면 된다는 것을 알게 되었다.

 

먼저, 생성 정점의 경우 '그래프들과 무관한 정점'이라는 점에서 들어오는 간선은 존재하지 않고, 나가는 간선만 존재한다. 나가는 간선은 2개 이상이어야 생성 정점이다! → 제한 사항에 그래프의 합은 2이상이라고 되어 있음

또한, 나가는 간선의 개수 = 생성 정점으로 연결하기 전 그래프의 총 개수이다.

 

막대 모양 그래프의 경우 다른 두 그래프(도넛 모양, 8자 모양)의 형태와 다르게 마지막 정점은 들어오는 간선만 존재하고, 나가는 간선은 존재하지 않는다.

 

8자 모양 그래프의 경우 다른 두 그래프(막대 모양, 도넛 모양)의 형태와 다르게 중간에 있는 정점은 들어오는 간선이 2개, 나가는 간선도 2개 존재한다.

 

마지막으로, 도넛 모양 그래프는 그래프의 총 개수 - 막대 모양 그래프 개수 - 8자 모양 그래프 개수의 값이다.

 

따라서, 정리하면 아래와 같은 특징을 이용해 문제를 해결할 수 있다.

	들어오는 간선의 개수	나가는 간선의 개수
생성 정점	0	2개 이상
막대 모양 그래프	1	0
8자 모양 그래프	2	2
도넛 모양 그래프	생성 정점 나가는 간선 개수 - 막대 모양 그래프 개수 - 8자 모양 그래프 개수

 

코드

function solution(edges) {
    // 들어오는 간선의 개수와 나가는 간선의 개수 카운팅
    const edgesInfo = new Map();
    for(const [a, b] of edges) {
        // 나가는 간선의 개수 증가
        if(edgesInfo.has(a)) {
            const [inCnt, outCnt] = edgesInfo.get(a);
            edgesInfo.set(a, [inCnt, outCnt+1]);
        }else edgesInfo.set(a, [0, 1]);
        
        // 들어오는 간선의 개수 증가
        if(edgesInfo.has(b)) {
            const [inCnt, outCnt] = edgesInfo.get(b);
            edgesInfo.set(b, [inCnt+1, outCnt]);
        }else edgesInfo.set(b, [1, 0]);
    }
    
    const answer = [0, 0, 0, 0];
    const nodes = [...edgesInfo];
    for(const node of nodes) {
        const [inCnt, outCnt] = node[1];
        // 생성 정점 찾기
        if(inCnt === 0 && outCnt >= 2) {
            answer[0] = node[0];
        } else if(outCnt === 0) { // 막대 그래프 찾기(나가는 간선이 0개)
            answer[2] += 1;
        } else if(inCnt >= 2 && outCnt >= 2) { // 8자 그래프 찾기(들어오는 간선, 나가는 간선 모두 2개 이상)
            answer[3] += 1;
        }
    }
    answer[1] = edgesInfo.get(answer[0])[1] - answer[2] - answer[3]; // 도넛 그래프 찾기
    
    return answer;
}