[프로그래머스] 도넛과 막대 그래프 (Python, 2024 카카오 winter internship)

프로그래머스

 

문제

• 도넛 모양, 막대 모양, 8자 모양의 그래프가 있음

• 도넛 모양 그래프
  • 크기가 n이면 n개의 정점, n개의 간선이 존재
  • 아무 정점에서 출발해 방문한 적 없는 간선을 따라가면 나머지 n-1개의 정점들을 한번씩 방문하고 출발했던 정점으로 돌아옴
• 막대 모양 그래프
  • 크기가 n이면 n개의 정점, n-1개의 간선이 존재
  • 임의의 한 정점에서 출발해 간선을 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 하나 존재
• 8자 모양 그래프
  • 크기가 n이면 2n+1개의 정점, 2n+2개의 간선이 존재
• 정점을 하나 생성하고 난 후 도넛, 막대, 8자 모양 그래프를 이루는 정점들 중 임의의 하나로 향하는 간선들을 연결
• 그래프의 간선 정보가 주어지면 `생성한 정점의 번호`와 `정점을 생성하기 전 도넛`, `막대`, `8자` 모양의 `그래프 수` 구하기

 

입출력

• 입력
  • `edges`: [[2,3],[4,3],[1,1],[2,1]]
• 출력
  • `result`: [2,1,1,0] 
  • 출력 순서: 추가한 정점 번호, 도넛 모양 그래프 수, 막대 모양 그래프 수, 8자 모양 그래프 수

 

제한 사항

• 1 <= `edges`의 길이 <= 1,000,000
  • edges의 원소는 [a,b] 형태고, a번 정점에서 b번 정점으로 향하는 간선임
  • 1 <= `a`, `b` <= 1,000,000
• 도넛 모양 그래프의 수 + 막대 모양 그래프의 수 + 8자 모양 그래프의 수 >= 2

 

---

 

풀이 아이디어

문제를 보고 제가 딱 떠올린 방법은 `정점들이 edges로 연결됨을 나타내는 2차원 배열 graph 만들기` 였습니다.

 

`[[2,3],[4,3],[1,1],[2,1]]` 입력을 예시로 들자면 `[[1,0,0,0],[1,0,1,0],[0,0,0,0],[0,0,1,0]]` 형태로 정점들이 연결되어 있는지 여부를 그래프로 변환하려고 했습니다. 그런 다음 도넛, 막대, 8자 모양 그래프인지 아닌지를 구분하는 코드를 queue와 visited 배열로 작성하려 했습니다. 

 

하지만 1번 정점부터 탐색을 시작한다고 가정했을 때 1번 정점이 추가로 생성된 정점인지 아닌지 먼저 확인해야 한다고 생각했고, 나가는 간선과 들어오는 간선의 개수로 파악할 수 있다는 것을 떠올렸습니다. 이 방법을 떠올린 후 막대, 도넛, 8자 그래프들도 각 정점에 들어오는 간선과 정점에서 나가는 간선의 개수로 구별할 수 있고, 기존에 BFS를 사용해 문제를 해결하려던 방법보다는 쉽게 풀 수 있다는 판단을 했습니다.

 

따라서 간선의 개수로 그래프의 모양을 구별하는 코드를 작성했습니다.

우선 `제한 사항`의 `도넛 모양 그래프의 수 + 막대 모양 그래프의 수 + 8자 모양 그래프의 수 >= 2` 조건으로 `추가로 생성된 정점`은 나가는 정점이 2개 이상이어야 한다는 것을 알 수 있었습니다.

 

막대 모양 그래프의 정점은 들어오는 간선은 1개, 나가는 간선은 0개입니다. 

그런데 아래의 막대 모양 그래프 사진을 보시면 나가는 간선이 1개고, 들어오는 간선이 0개인 것 아니냐고 의문을 갖게 되실 수 있습니다. 시각적으로는 화살표가 위쪽을 향하고 있어서 위에 있는 노드로 간선이 나가고, 들어오는 간선은 없다고 보일 수 있습니다. 하지만 각 그래프를 하나의 생성 정점으로부터 퍼져나가는 구조로 보기 때문에 `특징 노드`인 `끝나는 정점을 봐야` 막대 그래프의 끝점인지 도넛 그래프의 끝점인지 8자 그래프의 끝점인지 구분할 수 있습니다.

 

 

 

막대 그래프가 아래와 같이 연결되어 있을 때를 가정해 봅시다.

1 -> 2 -> 3 -> 4

 

시작 노드는 각각 들어오는 간선이 0개, 나가는 간선이 1개, 중간 노드는 들어오는 간선이 1개, 나가는 간선이 1개입니다. 결국 막대 그래프를 찾기 위한 `특징 노드`는 끝점이라는 것을 알 수 있습니다. 따라서 막대 모양 그래프는 들어오는 간선이 1개 이상(추가된 정점이 연결될 수 있기 때문), 나가는 간선이 0개입니다. 

노드	들어오는 간선	나가는 간선	의미
1	0	1	시작점 (생성 정점과 연결되어 있음)
2	1	1	중간
3	1	1	중간
4	1	0	끝점 (막대 그래프의 종단)

 

그럼 8자 모양 그래프의 `특징 노드`는 무엇일까요?

8자 모양 그래프는 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프이기 때문에 아래 사진의 빨간 동그라미와 같이 연결된 부분의 정점이 특징 노드인 것을 알 수 있습니다. 8자 모양 그래프의 특징 노드는 들어오는 간선 2개 이상(추가된 정점이 연결될 수 있기 때문), 나가는 간선이 2개입니다.

 

 

막대 모양 그래프와 8자 모양 그래프에서는 `특징 노드`를 찾을 수 있었지만 도넛 모양 그래프는 `특징 노드`가 없어 위와 같은 방법으로 개수를 구하기 어렵습니다. 도넛 모양 그래프에서는 모든 정점이 들어오는 간선 1개, 나가는 간선 1개이니까 찾을 수 있는거 아니냐는 의문을 갖을 수 있지만 8자 모양 그래프의 대부분의 노드들도 대부분 들어오는 간선 1개, 나가는 간선 1개이므로 도넛 모양 그래프만의 고유 특징이 아닙니다. (8자 모양 그래프와 같은 특징을 갖는 이유는 8자 모양 그래프가 도넛 모양 그래프를 연결해놓은 그래프이기 때문)

 

 

 

 

따라서 조건에서 주어진 `도넛 모양 그래프의 수 + 막대 모양 그래프의 수 + 8자 모양 그래프의 수 >= 2`을 이용할 예정입니다. 추가 생성된 정점에서 나가는 간선 수 - (막대 + 8자)를 하게 되면 도넛 모양 그래프 수를 구할 수 있습니다.

 

---

코드

def solution(edges):
    answer = [0,0,0,0]
    
    # 주어진 edges를 이용해 정점의 개수를 구합니다
    nodes = []
    for u, v in edges:
        nodes.append(max(u,v))
    max_val = max(nodes) + 1
    
    # 들어오는 정점, 나가는 정점 개수를 1차원 배열에 표현합니다.
    in_cnt, out_cnt = [0] * max_val, [0] * max_val
    for out_edge, in_edge in edges:
        out_cnt[out_edge] += 1
        in_cnt[in_edge] += 1
    
    # 생성된 정점: 들어오는 간선 0개, 나가는 간선 2개 이상
    # 막대: 들어오는 간선 1개 이상, 나가는 간선 0개
    # 8자: 들어오는 간선 2개 이상, 나가는 간선 2
    # 도넛: 생성된 정점을 나가는 간선의 수 - 막대 - 8자
    for node in range(1, max_val):
        if in_cnt[node] == 0 and out_cnt[node] >= 2:
            answer[0] = node
        elif in_cnt[node] >= 1 and out_cnt[node] == 0:
            answer[2] += 1
        elif in_cnt[node] >= 2 and out_cnt[node] == 2:
            answer[3] += 1
    
    answer[1] = out_cnt[answer[0]] - sum(answer[2:])
            
    return answer