[백준] 13023 파이썬(python) : ABCDE - (★)

13023번 : ABCDE

 

 

import sys
n, m = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
visit = [False] * (n+1)
res = False

def dfs(idx, depth):
    global res
    if depth == 4: #1
        res = True
        return
    for i in graph[idx]:
        if not visit[i]:
            visit[i] = True
            dfs(i, depth+1)
            visit[i] = False
for i in range(n):
    visit[i] = True
    dfs(i, 0)
    visit[i] = False
    if res == True:
        break
if res:
    print(1)
else:
    print(0)

 

이전 포스팅에서의 백트래킹 문제랑 비슷하다. 문제에서 원하는것은 A->B->C->D->E 관계를 가지면 1을 출력하라는 것인데 이말은 즉 끊기지 않고 4번 이어지는 트리의 구조를 가지고 있으면 된다는 뜻이다.

그래서 #1에서 재귀호출이 4가 되면 리턴하는것이다.

 

괜찮다. 이제 그래프이론 50문제 풀기의 첫번째 문제다. 할 수 있다:)

 

 

 

그림과 함께 좋은 설명을 해준 블로그가 있어서 링크를 걸어둔다.