[백준`G5] 13023 - ABCDE (Python)

문제 설명

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

13023번: ABCDE

 

성능 요약

메모리: 31120 KB, 시간: 1592 ms

분류

백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 3월 8일 01:32:29

문제 설명

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을 출력한다.

 

---

문제 풀이

 

인덱스마다 친구 목록을 저장해놓고, 첫 번째 친구(인덱스 0)부터 dfs를 실행하며 확인했다.

dfs에서는 친구 목록에서 하나씩 타고타고 내려가며 깊이 우선 탐색을 했다.

dfs로 깊이가 4가 되면 result를 바꾸고 출력

 

n, m = list(map(int, input().split()))
friend = [[] for _ in range(n)]
result = 0

for _ in range(m):
    a, b = list(map(int, input().split()))
    if b not in friend[a]:
        friend[a].append(b)
    if a not in friend[b]:
        friend[b].append(a)


def dfs(num, count, visited):
    global result
    if count == 4:
        result = 1
        return

    visited[num] = True
    for f in friend[num]:
        if not visited[f]:
            visited[f] = True
            dfs(f, count + 1, visited)
            visited[f] = False


for i in range(n):
    visited = [False] * n
    dfs(i, 0, visited)
    if result:
        break

print(result)