[Python/코테] 2024 Kakao Winter Internship - 2. 도넛과 막대 그래프

문제 링크: https://school.programmers.co.kr/learn/challenges?order=recent&page=1&partIds=58464

코딩테스트 연습 | 프로그래머스 스쿨

---

#2 도넛과 막대 그래프

알고리즘 설계

💡idea.

1. 생성된 정점과 각 그래프의 특징을 파악한다. → 나가는 간선 갯수와 들어오는 간선 갯수로 모든 특징을 구분할 수 있다.

• 생성된 정점: 나가는 간선이 2개 이상(그래프의 개수) 존재하고, 들어오는 간선이 존재하지 않습니다.
• 막대 모양 그래프: 생성된 정점과 연결된 간선을 제외했을 때, 들어오는 간선이 없는 정점이 하나 존재하고, 나가는 간선이 없는 정점이 하나 존재합니다(두 정점은 같을 수 있습니다). 나머지 정점은 나가는 간선과 들어오는 간선이 하나씩 존재합니다. 
• 도넛 모양 그래프: 생성된 정점과 연결된 간선을 제외했을 때, 모든 정점이 나가는 간선과 들어오는 간선이 하나씩 존재합니다.
• 8자 모양 그래프: 생성된 정점과 연결된 간선을 제외했을 때, 1개의 정점을 제외하면 나가는 간선과 들어오는 간선이 하나씩 존재합니다. 1개의 정점은 나가는 간선 2개와 들어오는 간선 2개가 존재합니다.

2. 1번에서 찾은 특징에 의해, 그래프 전체를 구현하기보다 나가고 들어오는 간선의 정보를 담은 변수를 활용한다.

3. 그래프를 찾기 위해 BFS를 활용한다.

 

🐧해설 참고

도넛과 막대 그래프 (프로그래머스, 2024 카카오 겨울 인턴십, Python)

2024 카카오 겨울 인턴십 코딩테스트 문제해설

알고리즘 구현

코드 출처: https://velog.io/@oxboxx/%EB%8F%84%EB%84%9B%EA%B3%BC-%EB%A7%89%EB%8C%80-%EA%B7%B8%EB%9E%98%ED%94%84-Python

from collections import deque


def solution(edges):
    MAX_LENGTH = 1_000_001

    out = [[] for _ in range(MAX_LENGTH)]
    come = [[] for _ in range(MAX_LENGTH)]

    for s, e in edges:
        out[s].append(e)
        come[e].append(s)

    # 시작점 찾기
    start = -1
    for node in range(MAX_LENGTH + 1):
        # 들어오는 정점은 2개 이상, 나가는 정점이 0개일 때 -> 생성된 정점
        if len(come[node]) == 0 and len(out[node]) >= 2:
            start = node
            break

    answer = [start, 0, 0, 0]
    visited = [False] * (MAX_LENGTH)

    # 그래프를 찾기위한 BFS 정의
    def bfs(i):
        q = deque([i])
        visited[i] = True

        while q:
            node = q.popleft()
            if not out[node]:  # 막대 그래프 - 마지막 노드에서 나가는 간선이 없음
                answer[2] += 1
                return
            # 8자 그래프 - 중간에 나가는 경로와 들어오는 경로가 모두 2인 노드가 있다.
            if len(out[node]) == 2 and len(come[node]) == 2:
                answer[3] += 1
                return

            for next in out[node]:
                if not visited[next]:
                    visited[next] = True
                    q.append(next)

        answer[1] += 1

    for node in out[start]:
        come[node].remove(start)    # 생성된 정점과 연결된 간선 모두 삭제(연결 끊음)
        bfs(node)   # 생성된 정점에서 BFS 실행

    return answer

나다어

• 파이썬에서 그래프는 딕셔너리, 혹은 2차원 배열로 구현 가능하다.

graph = {1: [2, 3], 2: [3], 3: [4], 4: [], 5: [1, 4]}
graph2 = [[], [2, 3], [3], [4], [], [1, 4]]

 

• 사전형 변수에서 key 값을 추가해서 value를 초기화하려면 if 조건문에 not in 연산자를 활용한다.
• 계산할 때마다 큰 범위의 for문을 반복해야 한다면, 따로 계산된 변수를 두는 것도 방법이다!
     해당 풀이의 경우, 특정 정점에서 나가는 간선의 갯수와 들어오는 간선의 갯수를 매번 계산하지 않고, 초기화 시 계산해주었다.
      또한, 그래프 전체를 하나의 변수로 구현하지 않고 문제에 필요한 정보만을 변수로 만들었다.
• 문제 상황을 바꿔서(나눠 보기, 삭제하기, ..) 풀린다면 크게 2단계로 나누어 풀어도 된다. 
     해당 풀이의 경우, 생성된 정점을 먼저 찾고 그 정점을 배제(간선 삭제)시킨 뒤 나머지 그래프를 세는 방식으로 진행했다.