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

13023번: ABCDE

분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색(DFS)
• 백트래킹

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

풀이

A-B-C-D-E처럼 일렬로 연결되는 관계가 5명 이상이면 1을 아니면 0을 출력해야 한다. DFS로 말하자면 깊이가 5인 관계가 존재하는지의 여부를 계산해야 한다.

따라서 친구관계를 인접리스트로 만들어서 방문여부를 체크하면서 DFS를 실행해야 한다.

DFS를 돌아나올때 방문했던 곳을리셋해주는 것을 잊지 말자!

코드

def dfs(level,i):
    global flag
    if level==4:
        flag = 1
        return
    for k in friend[i]:
        if visited[k]==0:
            visited[k]=1
            dfs(level+1,k)
            visited[k]=0

N,M=map(int, input().split())
friend=[[] for _ in range(N)]

for _ in range(M):
    a,b=map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)
    
flag=0
for i in range(N):
    if friend[i]:
        visited=[0]*N
        visited[i]=1
        dfs(0,i)
    if flag:
        break
if flag:
    print(1)
else:
    print(0)

지극히 개인적인 풀이로 좋은 코드가 아닐 수 있습니다.