[알고리즘 문제 풀이][파이썬] 백준 13023번: ABCDE

백준 13023 문제 링크: https://www.acmicpc.net/problem/13023

📑 문제 설명
1. 5명 이상 2000명 이하의 사람이 존재
2. 사람들 중에서 다음과 같은 친구관계가 존재하는 지 조사
A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
3. 위와 같은 친구 관계가 존재할 경우 1을, 존재하지 않을 경우 0을 출력

입력: 첫째 줄에는 사람의 수 N과 친구 관계의 수 M이 주어지고 둘째줄부터 M+1줄까지 어떤 친구관계가 있는지 입력

출력: 문제 설명 2번과 같은 친구관계가 존재할 경우 1을, 그렇지 않을 경우 0을 출력

💡 문제 해결 방법
알고리즘: DFS

알고리즘 선택 이유
1. 한 친구를 탐색하고 그 다음 친구를 탐색하고 깊게 들어가야 하기 때문에

예외처리 및 추가 내용
1. 친구 관계는 4쌍으로 구성되면 된다.(1-->2-->3-->4-->5)
2. dfs를 돌리고 나서 5명이 되면(==dist가 4가 되면) 바로 return하고 모든 버택스에서 조사를 했는데도 5명이 안된다면 그 때 0을 출력한다.
3. 친구관계에 방향성이 존재하지 않으므로 1과 2가 친구라면 1에도 2를, 2에도 1을 추가해야 한다.
4. 방향성이 없기 때문에 재귀에서 탈출할 경우 종료조건(2번)이 아니라면 다시 재탐색이 가능하므로 방금 들린 노드는 다시 'False'로 처리해야 함

스터디 내용
1. dist=4인 애들이 있느냐
2. find all path 하라는 문제
- dfs + 백트래킹

💻 코드

import sys

def dfs(node, dist):
    global maxdist
    visit[node] = True
    maxdist = max(dist, maxdist)
    if dist >= 4:
        return
    for next_node in graph[node]:
        if visit[next_node] == False:
            dfs(next_node, dist+1)
            visit[next_node] = False

n, m = list(map(int, sys.stdin.readline().split()))
graph = {}
for i in range(n+1):
    graph[i] = []
for i in range(m):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a].append(b)
    graph[b].append(a)


global maxdist
maxdist = -1
check = False
for i in range(0,n+1):
    visit = [False for x in range(n+1)]
    dfs(i, 0)
    if maxdist >= 4:
        print(1)
        check=True
        break
if check == False: print(0)

💟 추가적으로 알게 된 점