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

일단 문제부터 해석하기가 어려웠음.

따라서, 그냥 문제를 읽고 생각의 흐름만 정리해봄.

해당 입력에서 '생성한 정점 노드가 2' 라는 의미가 도무지 무슨 말인지 이해가 가지 않았다.

이해한 결과는 먼저, 총 3가지의 그래프의 종류 [ 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프 ]가 존재하는데 이것들을 별도로 생성한 다음 해당 그래프들과 '하나의 정점'이 위의 3가지 종류의 그래프들을 잇는 역할을 한다는 것이다.

 이제 얼추 문제를 파악했으니, 어떻게 edge들의 집합으로만 3가지 종류의 그래프를 구분할 수 있을지 고민해 보자.

 가장 어려울 듯한 모양이 '8자 모양'인 듯하다. 8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프입니다. 결국 도넛 모양 그래프를 분류하는 부분과 분명히 중복되는 부분이 있을것으로 예상됨.

 

 먼저, 각 모형별 특징점에 대해서 고민해 보자.

도넛 모양 그래프는 cylic 여부를 먼저 따지면 가능할 것이라고 생각함.

다음, 막대 모양은 위와 반대로 acylic한 성질을 만족할 것으로 생각된다.

마지막, 8자 모형은 cylic하지만, 해당 nodes 중 edge를 4개 포함 node가 존재한다면, 8자 형이라고 생각함.

일단, 이 정도로 조건 파악을 해놓고 문제를 풀면서, 더 고민하기로 함.

 

 그러면 해당 edges를 어떻게 정리를 해야하나 자료구조를 고민을 해보자.

1. 2차원 배열로 만들다. (1,000,000 X 1,000,000) 배열이라니,, 너무 커서 메모리 리미트에 맞추기 어려울 듯하다..

2. 딕셔너리 형태로 각 node들이 갈 수 있는 다음 node들을 value로 저장한다.-->일단 okay

3. map으로 저장한다. 첫 번째 원소들로 정렬이 되서 좋은 점은 있지만, 이후 접근할때 다시 연산이 필요하여 --> 딕셔너리가 더 나음

 

이 정도 생각으로 2번 딕셔너리 구조로 만들기로 결정함.

이 생각을 하면서 C++에서는 마치 linked list가 떠올랐고, 위에서 특정 node에 4개 이상의 edge(해당 node에 시작 node의 edge가 들어와서 5개가 될 수도 있으므로..)가 있다면, 8자형의 중심 node(1) 혹은 시작 node(2) 둘 중 하나일 거라는 생각이 들었다.

이때, '정점 노드'는 받는 edge가 존재하지 안혹 오로지 나가는 edge만 2개 이상 존재한다는 점에서 전체적인 dictionary 구조를 해당 노드로부터 나가는 쪽, 받는 쪽으로 2가지 정보를 갖도록 만들어야 되지 않나? 라고 생각함

 

이제 마지막로 다시 각 그래프를 구분할 수 있는 조건들을 정해야한다.

1. 정점 노드는 2개 이상의 그래프를 가리키기 때문에, (들어오는 edge == 0, 나가는 edge는 2 이상) 조건으로 찾을 수 있다.

2. 8자 모형 그래프는 처음에는 총 4개의 edge만 갖고 있는 다면 충분할 것이라고 생각했지만, 위 정점 노드에서 4개의 그래프를 가리킬 수 있으므로, 더 구체적인 조건이 필요하다는 것을 깨달았다. 따라서 (들어노는 edge == 2, 나가는 edge ==2)를 만족하는 노드 수가 곧 그래프 수와 일치한다.

3. 여기서 고민이 많았다. 도넛 모양과 막대 모양 딱 두 개만 정확하게 분간할 수 있는 방법이 cyclic 검출 밖에 없다고 생각을 했기 때문이다. 

  1) 도넛, 막대를 각각 계산하여서 구하는 방법

  2) 정점 노드에서 나가는 edge수는 결국 총 그래프의 개수 이므로 둘 중 하나만 구하면, 나머지 하나는 여집합으로 계산

   ----> 당연히 2)번 방법으로 진행 -> 그러면 둘 중 뭐를 구하지?..

   [1] 도넛을 구한다면, 방법은 cyclic검출 밖에 없는데, 이러면 결국, 모든 edge들을 순회해야함. worst O(n^2)

   [2] 막대를 구한다면, 방법은?...(이거 생각하는데 상당히 오래걸림...ㅠ)

       ==> 막대는 항상 마지막 node는 갈 곳이 없다는 것이다. 즉, 받는 edge는 존재하지만 나가는 edge가 없는 node 개수

 

 

정리하면 조건들은 다음과 같다.

정점 노드 구하기
들어오는 edge = 0 & 나가는 edge >= 2

그래프 개수 구하기
[8자 모형 그래프]
들어오는 edge >= 2 & 나가는 edge = 2 의 node 수 (2 이상인 이유는 정점 노드가 가리킬 수 있으므)
[막대 모형 그래프]
들어오는 edge >= 1 & 나가는 edge = 0인 node 수 (1 이상인 이유는 정점 노드가 가리킬 수 있으므로)
[도넛 모형 그래프]
전체 그래프 개수 - [8자] - [막대]

 

 

def make_dict(edges):
    ans = {}
    # key, value[0]-->나가는 엣지, value[1]-->들어오는 엣지
    for edge in edges:
        start = edge[0]
        end = edge[1]
        ans.setdefault(start, [[],[]])[0].append(end)
        ans.setdefault(end, [[],[]])[1].append(start)
    return ans


def solution(edges):
    graph = make_dict(edges)
    answer = [0, 0, 0, 0]
    for key, value in graph.items():
        out = len(value[0])
        in_ = len(value[1])
        if in_ == 0 and out >= 2:
            answer[0] = key
            pivot = out
        elif in_ >= 2 and out == 2:
            answer[3] += 1
        elif in_ >= 1 and out == 0:
            answer[2] += 1
    answer[1] = pivot - answer[2] - answer[3]
            
    return answer

상당한 runtime을 가진 것을 확인

 

 

[다른 사람의 풀이]

가장 처음 제안된 풀이는 약간의 효율성이 높았지만, test case 35번을 통과시키지는 못하였다.