[Programmerse] Level2 도넛과 막대 그래프

문제 요약

• 알고리즘 분류: 그래프
• 난이도: Level2
• 문제 요약
  • 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있다.
  • 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있다.
  • 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 된다. 도넛 모양 그래프의 형태는 다음과 같다.

• 크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재한다. 막대 모양 그래프의 형태는 다음과 같다.

 

• 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있다. 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프이다. 8자 모양 그래프의 형태는 다음과 같다.

• 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구하여라.
• 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상이다.
• 사이트 주소: https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

문제풀이

  이번 문제는 그래프 자료구조에 대한 문제이다. 그래프에 대한 자세한 설명은 아래 글에 확인 해보면된다.

https://jih3508.tistory.com/100

[알고리즘 이론] 그래프(Grape)

 그래프 관련 문제이지만 정점의 특징만 알면 문제 풀기가 쉬울 것이다. 프로그래머스 예제를 2개를 보면

검은 색은 정점노드, 빨간색은 도넛, 파란색은 막대, 주황색은 8자 막대이다.

 

그림에서 3개의 그래프와 정점노드의 특징을 보면 아래와 같다.

• 정점노드: 들어오는 간선이 없고 나가는 간선이 2개 이상이다.
• 막대 그래프: 나가는 간선이 없고 들어오는 간선이 1개 이상이다.
• 8자 그래프: 나가는 간선 2개 들어오는 간선 2개 이상이다.
• 도넛 그래프: 정정노드 나가는 간선 - 막대 그래프 개수 - 8자 그래프

정점 노드는  문제 에서 아래 글 보면 3개 그래프 합은 2개 이상 이기 때문에  나가는 간선이 2개 이상인것만 확인하면 된다.

 

막대 드래프는 첫번째 그림 3번 노느와 두번째 그림 2번 노드를 보면  들어오는 간선만 있고 나가는 간선만 들어 와 있는 것을 확인 해볼수 있다.

8자 그래프는 두번째 그림 3번 노드와 11번 노드를 보면 된다. 8자 모양의 중심점이다. 자세히 보면 가는 간선 2개 들어노는 간선 2개 이상인것을 확인할수 있다.

 구현은 아래와 같이 정리 할수 있다.

1.  key-value 자료구조로 key값은 노드 value는 크기 2인 배열 또는 리스트로 선언 한다. 하나는 들어오는 간선 개수 나가는 간선개수를 추가한다.
2. 각 key마다 위에 조건에 맞게 정점노드, 막대 그래프, 8자 그래프 개수를 구한다.
3. 도넛 그래프는 위 조건에 맞게 저장한다. 

이번 문제는 BFS나 DFS로 풀수 있지만 그래프 탐색 알고리즘 방법으로 풀수 있지만 구현해야될 코드와 시간 복잡도가 더 걸리수 있다. 하지만 위 방법으로 풀면  O(V+E)에 문제 해결이 가능한다.

Code

Python

def solution(edges):
    answer = [0, 0, 0, 0]

    nodeCnt = dict({})
    for edge in edges:
        a = edge[0]
        b = edge[1]
        # 나가는것, 들어것 개수를 저장한다.
        if not nodeCnt.get(a):
            nodeCnt[a] = [0, 0]
        if not nodeCnt.get(b):
            nodeCnt[b] = [0, 0]
        nodeCnt[a][0] += 1
        nodeCnt[b][1] += 1

    for key, cnts in nodeCnt.items():

        # 나가는 간선이 2개이상 들어오는 간선이 0개인것을 생성점
        if cnts[0] >= 2 and cnts[1] == 0:
            answer[0] = key
        # 나가는 간선이 없고 들어오는 간선 1개 이상일때 막대 그래프 개수 추가
        elif cnts[0] == 0 and cnts[1] > 0:
            answer[2] += 1
        # 들어오는 간선 2개 이상 나가는 간선 2개 이상일때 8자 모양 그래프 개수 추가
        elif cnts[0] >= 2 and cnts[1] >= 2:
            answer[3] += 1
    # 점정에서 나가는 간선에서 막대 그래프 8자 모양 제외한것이 8자 모양 그래프임
    answer[1] = nodeCnt[answer[0]][0] - answer[2] - answer[3]
    return answer

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] solution(int[][] edges) {
        Map<Integer, int[]> nodeCnt = new HashMap<>();
    	int[] answer = {0, 0, 0, 0};
    	
    	Arrays.stream(edges).forEach(edge -> {
    		int a = edge[0];
    		int b = edge[1];
    		if(!nodeCnt.containsKey(a)) {
    			nodeCnt.put(a, new int[] {0, 0});
    		}
    		if(!nodeCnt.containsKey(b)) {
    			nodeCnt.put(b, new int[] {0, 0});
    		}
    		// 가는것, 들어오는것 카운터임
    		nodeCnt.get(a)[0] += 1;
    		nodeCnt.get(b)[1] += 1;
    	});
    	
    	int[] cnts;
    	for(int key : nodeCnt.keySet()) {
    		cnts = nodeCnt.get(key);
    		
    		// 들어오션 노드가 없고 나가는 노드가 2개 이상일때 정점이 된다.
    		if(cnts[0] >= 2 && cnts[1] == 0 ) {
    			answer[0] = key;
    		// 들어오는 정점의 개수가 막대 그래프임 개수
    		}else if(cnts[0] == 0 && cnts[1] > 0) {
    			answer[2]++;
    		// 들어오는것 나가는것 각 2개 이상인 점의 개수는 8자 그래프의 개수
    		}else if(cnts[0] >= 2 && cnts[1] >= 2) {
    			answer[3]++;
    		}
    	
    	}
    	
    	// 점정 나가는 노드 수가 막대와 8자를 제외한것이 도넛 그래프의 개수
        answer[1] = nodeCnt.get(answer[0])[0] - answer[2] - answer[3];
        
        return answer;
    }
}