[프로그래머스] 도넛과 막대 그래프 (2024 카카오 코테)

 

(( 한 번 더 보기 ))

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=python3#

프로그래머스

 

 

 

 

TIL

• IT 기업의 코테 문제는 시간 초과를 매우 많이 신경 써야함!! 
  • 실제 코테에선 모든 테스트케이스가 주어지지 않기 때문에, 꼭 주어진 범위와 시간 생각해야함
• 엣지 케이스 신경쓰는 연습하기 !! 
  • 마찬가지로 실제 코테에선 여러 개의 테스트케이스가 주어지지 않기 때문에 고려해서 생각해야 함
• 그래프 문제 
  • out edge 와 in edge의 특성을 잘 사용하기
  • 두 개를 나눠서 확인하는 방법도 가능하다는 거 잊지말기 (이번 문제는 그렇게 풀어야만 시간 초과없이 성공)
• 문제를 풀기 전에 열심히 적기 >> 문제를 풀기 위한 관찰 필수
  
  • 사소해 보이는 것이라도 일단 적어놓기
  • 하나의 특징으로 뽑아내는 것이 불가능하다면 여러 개 조합해서 뽑아내기 !!!!!
• 파이선 재귀 깊이 제한은 1000번 !! >> 무조건 setrecursionlimit을 통해 늘려놓기 (안그럼 런타임에러 발생)

 

[ 처음 코드 ] - dfs로 모든 노드와 간선의 개수 구한 뒤, 두 수의 관계를 통해서 그래프 분류 >> 정답이지만 시간 초과

# 정점은 in 간선은 한 개도 없음, out은 무조건 있음 >> stick도 이럴 수 있음
# 정점은 out 간선이 1개 이상 >> 도넛모양도 2개임 ㅠㅠ
# 어떻게 정점을 찾을것인가 >> 여러 특징을 조합해서 찾아야함 !!!!!!

from collections import defaultdict, deque

# 계속 시간 초과가 나는데 find_one 부분이 문제인 거 같음
# 현재 시간복잡도 O(N^2)
def find_one(edges):
    out_edge = defaultdict(int)
    in_edge = set()
    for v1, v2 in edges:
        out_edge[v1] += 1
        in_edge.add(v2)
    
    # 이 부분에서 오류 발생했던 것 
    # out_edge[o] > 1 이거 추가 (위에 썼듯이 stick도 조건 만족해서 무조건 2개 이상의 out으로 간주, 문제조건에도 그래프는 2개 이상이라 되어있음)
    for o in out_edge:
        if o not in in_edge and out_edge[o] > 1:
            return o

def find_graph(node, graph):  # start node
    # donut, stick, eight : 1, 2, 3
    vertex = set()
    visited = [False for _ in range(1000000)]
    queue = deque()
    queue.append(node)
    vertex.add(node)
    
    num_edge = 0
    while queue:
        n = queue.popleft()
        visited[n] = True

        for neighbor in graph[n]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True
            vertex.add(neighbor)
            num_edge += 1
    
    num_vertex = len(vertex)
    num_edge //= 2
    # print(f"num_vertex: {num_vertex}, vertex: {vertex}")
    # print(f"num_edge:{num_edge}")
    
    if num_edge == num_vertex:  # donut
        return 1
    elif num_edge+1 == num_vertex:  # stick
        return 2
    elif (num_edge-2)/2 == (num_vertex-1)/2:    # else: return 3
        return 3


def solution(edges):
    
    one = find_one(edges)
    start_node = []
    for v1, v2 in edges:
        if v1==one:
            start_node.append(v2)
    
    graph2 = defaultdict(list)
    for v1, v2 in edges:
        if v1!=one:
            graph2[v1].append(v2)
            graph2[v2].append(v1)

    donut = stick = eight = 0
    for i in start_node:
        ans = find_graph(i, graph2)
        if ans == 1 : # donut
            donut += 1
        elif ans == 2:  # stick
            stick += 1
        elif ans == 3:  # eight
            eight += 1
    
    return [one, donut, stick, eight]

 

 

 

 

Code

# 정점은 in 간선은 한 개도 없음, out은 무조건 있음 >> stick도 이럴 수 있음
# 정점은 out 간선이 1개 이상 >> 도넛모양도 2개임 ㅠㅠ
# 어떻게 정점을 찾을것인가 >> 여러 특징을 조합해서 찾아야함 !!!!!!

from collections import defaultdict
# 재귀 구현 시, 무조건 이거 설정해두기 >> 안그럼 런타임 에러 발생ㅠㅠ
# 이 코드도 이거 안하니까 실패떳음 ..! 
# 파이썬은 기본으로 1000번까지 밖에 안됨
import sys
sys.setrecursionlimit(10**6)

# 계속 시간 초과가 나는데 find_one 부분이 문제인 거 같음
# 현재 시간복잡도 O(N^2)
def find_one(edges):
    out_edge = defaultdict(int)
    in_edge = set()
    for v1, v2 in edges:
        out_edge[v1] += 1
        in_edge.add(v2)
    
    # 이 부분에서 오류 발생했던 것 
    # out_edge[o] > 1 이거 추가 (위에 썼듯이 stick도 조건 만족해서 무조건 2개 이상의 out으로 간주, 문제조건에도 그래프는 2개 이상이라 되어있음)
    for o in out_edge:
        if o not in in_edge and out_edge[o] > 1:
            return o

def find_graph(node, graph):  # start node
    # donut, stick, eight : 1, 2, 3
    global visited
    if node in visited:
        return 1
    if not graph[node]:
        return 2
    if len(graph[node])==2:
        return 3
    visited.add(node)
    return find_graph(graph[node][0], graph)
    
def solution(edges):
    one = find_one(edges)
    start_node = []
    for v1, v2 in edges:
        if v1==one:
            start_node.append(v2)
    
    graph2 = defaultdict(list)
    for v1, v2 in edges:
        if v1!=one:
            graph2[v1].append(v2)
    
    global visited
    visited = set()
    donut = stick = eight = 0
    for i in start_node:
        ans = find_graph(i, graph2)
        if ans == 1 : # donut
            donut += 1
        elif ans == 2:  # stick
            stick += 1
        elif ans == 3:  # eight
            eight += 1
    
    return [one, donut, stick, eight]

• 매개변수로 "donut"을 반환하는 것보다 "1"을 반환하는 것이 시간 및 메모리 절약

 

 

 

[ 참고할 만한 코드]

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def solution(edges):
    G_out = defaultdict(list)
    G_in = defaultdict(int)
    visited = set()
    shapes = {"stick": 0, 'donut': 0, 'eight': 0}

    # 1. 그래프 만들기
    for a, b in edges:
        G_out[a].append(b)
        G_in[b] += 1

    # 2. root 찾기 (out이 2개 이상이고 in이 0개인 노드는 root 밖에 없음)
    root = [
        node
        for node in G_out
        if len(G_out[node]) >= 2 and G_in[node] == 0
    ][0]

    # 3. 모양 확인 함수 정의
    def find_shape(now: int):
        if now in visited:
            return 'donut'
        if not G_out[now]:
            return 'stick'
        if len(G_out[now]) == 2:
            return 'eight'
        visited.add(now)
        return find_shape(G_out[now][0])

    # 4. root로부터 연결된 그래프 모양 확인
    for next in G_out[root]:
        shape = find_shape(next)
        shapes[shape] += 1

    return [root, shapes['donut'], shapes['stick'], shapes['eight']]

 

• 이 코드는 dfs로 그래프의 모양을 다 확인하는 것이 아닌, 그래프 모양의 특징을 잡아 특정 부분만으로 그래프 확인
  • 따라서 시간이 훨씬 적게 걸림
• 참고하면 좋을 풀이 >> 풀이의 사고방식을 알아두면 좋을 듯 !!
  • https://school.programmers.co.kr/questions/82833