백준 - ABCDE(feat.Python)

https://www.acmicpc.net/problem/13023

• 처음에는 원소가 5개 이상인 그래프가 존재하면 되는 줄 알고, Disjoint Set문제인줄 알고 잠시 뻘짓을 했지만 그냥 깊이가 5 이상인 그래프를 찾는 문제였다

문제 요구사항

• 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
• 문제 조건의 친구 관계는 A->B->C->D->E 로 5개의 노드가 연결되어있으면 된다.

문제 풀이

• 1. 모든 노드를 한번씩 루트 노드로 삼고, dfs를 돌린다.
• 2 - 1. 깊이가 5를 만족하는 경우가 있을 시, 1을 출력하고 시스템 종료
• 2 - 2. 모든 순회를 마치고도 깊이가 5를 만족하는 경우가 없을 시 0을 출력

시간 복잡도는 O(V * (V+E)) = O(V^2)이다.(V, E 범위가 2000이므로 충분)

import sys
input = lambda : sys.stdin.readline().rstrip()

def dfs(x,cnt): #O(V+E)
    if cnt == GOAL:
        print(1)
        exit()
    for u in graph[x]:
        if not visited[u]:
            visited[u] = True
            dfs(u,cnt+1)
            visited[u] = False

if __name__ == '__main__':
    v, e = map(int, input().split())
    graph = [[] for _ in range(v)]
    GOAL = 5
    visited = [False] * v
    for _ in range(e):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)

    for i in range(v): # O(V)
        visited[i] = True
        dfs(i,1)
        visited[i] = False

    print(0)