[백준] 13023번: ABCDE

문제

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

13023번: ABCDE

 

풀이

백트래킹을 사용해 풀었습니다.

양방향 그래프로 a, b를 저장합니다.

모든 사람을 시작으로 그 중 하나라도 탐색 깊이가 5에 도달하면 solution()이 1을 반환하고, 도달하지 못하면 0을 반환합니다.

 

코드

파이썬

import sys

input = sys.stdin.readline

def solution():
    def DFS(x, L):
        nonlocal flag
        if flag:
            return
        if L == 5:
            flag = True
        else:
            for nx in graph[x]:
                if not check[nx]:
                    check[nx] = True
                    DFS(nx, L+1)
                    check[nx] = False

    N, M = map(int, input().split())

    flag = False
    graph = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    for i in range(N):
        check = [False] * N
        check[i] = True
        DFS(i, 1)
        if flag:
            return 1
    return 0

print(solution())