[프로그래머스] 258711. 도넛과 막대 그래프 | 그래프, BFS | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

• 도넛, 막대, 8자 그래프에 속하는 그래프 n개가 있다.
• 이 그래프들과 무관한 정점을 하나 만들고, 정점으로부터 다른 그래프들로 향하는 간선을 만든다.
• 무관한 정점은 몇번이고 무관한 정점을 제거하면 도넛/막대/8자 그래프의 개수는 몇개일까?

---

문제 조건

• 1 <= 간선의 길이 <= 1,000,000
• 도넛/막대/8자 그래프 수의 합 >= 2
• 크기가 n인 도넛 그래프는 n개의 정점과 n개의 간선으로 이루어져 있으며, 아무 한 정점에서 출발해 이용한적 없는 간선을 계속 따라가면 나머지 n - 1개의 정점들을 한번씩 방문한 뒤 원래 출발했던 정점으로 돌아온다.
• 크기가 n인 막대모양 그래프는 n개의 정점과 n-1의 간선으로 이루어져 있으며, 임의의 한 점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한번씩 방문하게 되는 정점이 단 하나 존재한다.
• 크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선으로 이루어져 있으며, 크기가 동일한 2개의 도넛 모양 그래프에서 정점을 하나씩 골라 결합시킨 형태의 그래프이다.

---

접근방법

무관한 정점의 진입차수는 0이고 진출차수는 2 이상이다. 

무관한 정점의 진출차수는 도넛/막대/8자 그래프 수의 합이다.

무관한 정점을 제거한 후 진입차수가 0인 정점의 수는 막대그래프의 수와 같다.

무관한 정점을 제거한 후 진입차수가 2인 정점의 수는 8자그래프의 수와 같다.

도넛그래프의 수는 총 그래프 수 - 막대그래프수 - 8자그래프수이다.

---

소스코드

테스트 8부터 26까지 시간초과 뜬 코드(나머지는 정답)

비록 시간초과는 떴지만 그래프의 정점과 간선의 개수를 조회하는 알고리즘을 작성해볼 수 있었다.

import copy

# start번째 정점이 포함된 그래프의 정점 리스트 반환
def getGetGraphVertexList(graph, vertexList, start):
    방문여부 = {v: False for v in vertexList}

    q = [start]
    while len(q) > 0:
        x = q.pop(0)
        방문여부[x] = True

        for y in vertexList:
            if graph[x][y] and not 방문여부[y]:
                q.append(y)

    return list(dict(filter(lambda x: x[1], 방문여부.items())).keys())


# 그래프의 정점수, 간선수 조회
def getVertexCntAndEdgeCnt(graph, graphVertexList):
    정점수 = len(graphVertexList)
    간선수 = 0
    for i in graphVertexList:
        for j in graphVertexList:
            if graph[i][j]:
                간선수 += 1

    return (정점수, 간선수)


# 그래프 제거
def deleteGraph(graph, vertexList, graphVertexList):
    for i in graphVertexList:
        for j in graphVertexList:
            if graph[i][j]:
                graph[i][j] = False

    for i in graphVertexList:
        vertexList.remove(i)


def solution(edges):
    # 정점리스트, 정점 최대값 조회
    vertexList = set()
    for (i, j) in edges:
        vertexList.add(i)
        vertexList.add(j)
    vertexList = list(dict.fromkeys(vertexList))
    sorted(vertexList)
    maxV = vertexList[-1]

    # edges를 graph(인접행렬)로 변환
    graph = [[False for j in range(maxV+1)] for i in range(maxV+1)]
    for (i, j) in edges:
        graph[i][j] = True

    # 진입/진출 차수 세기
    진입진출차수 = {}
    for i in vertexList:
        진출차수 = 진입차수 = 0
        for j in vertexList:
            if graph[i][j]:
                진출차수 += 1
            if i != j and graph[j][i]:
                진입차수 += 1

        진입진출차수[i] = (진입차수, 진출차수)

    # 무관한 정점 찾기
    무관한정점 = 0
    for k, v in 진입진출차수.items():
        진입차수, 진출차수 = v
        if 진입차수 == 0 and 진출차수 >= 2:
            무관한정점 = k

    # 무관한 정점 제거
    for i in vertexList:
        graph[무관한정점][i] = False
    vertexList.remove(무관한정점)

    # 도넛그래프, 팔자그래프 찾기
    도넛그래프수 = 팔자그래프수 = 0
    남은정점들 = copy.deepcopy(vertexList)
    for i in vertexList:
        if i not in 남은정점들:
            continue

        graphVertexList = getGetGraphVertexList(graph, 남은정점들, i)
        vc, ec = getVertexCntAndEdgeCnt(graph, graphVertexList)

        if vc == ec:
            도넛그래프수 += 1
            deleteGraph(graph, 남은정점들, graphVertexList)
        elif vc < ec:
            팔자그래프수 += 1
            deleteGraph(graph, 남은정점들, graphVertexList)

    # 막대그래프 찾기
    # 막대그래프수 = 진입차수 없는 정점 개수
    막대그래프수 = 0
    for i in 남은정점들:
        진입차수 = 0
        for j in 남은정점들:
            if graph[j][i]:
                진입차수 += 1

        if 진입차수 == 0:
            막대그래프수 += 1

    return [무관한정점, 도넛그래프수, 막대그래프수, 팔자그래프수]

 

최종통과한 코드

MAX_CNT = 1000001

def solution(edges):
    진입차수 = [0] * MAX_CNT
    진출차수 = [0] * MAX_CNT

    정점들 = set()
    for (i, j) in edges:
        진입차수[j] += 1
        진출차수[i] += 1
        정점들.add(i)
        정점들.add(j)

    정점들 = list(정점들)
    
    무관한정점 = 0
    for i in 정점들:
        if 진입차수[i] == 0 and 진출차수[i] >= 2:
            무관한정점 = i
            break

    # 그래프수 조회
    그래프수 = 진출차수[무관한정점]

    # 무관한 정점에 의한 진입차수 제거
    for (i, j) in edges:
        if i == 무관한정점:
            진입차수[j] -= 1
    정점들.remove(무관한정점)

    # 막대그래프수(진입차수가 0인 정점수) 조회
    막대그래프수 = 0
    for i in 정점들:
        if 진입차수[i] == 0:
            막대그래프수 += 1

    # 팔자그래프수(진입차수가 2인 정점수) 조회
    팔자그래프수 = 0
    for i in 정점들:
        if 진입차수[i] == 2:
            팔자그래프수 += 1

    # 도넛그래프수(그래프수 - 막대그래프수 - 팔자그래프수) 조회
    도넛그래프수 = 그래프수 - 막대그래프수 - 팔자그래프수

    return [무관한정점, 도넛그래프수, 막대그래프수, 팔자그래프수]