IT-garden

문제

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

예제 입력과 출력

정답

import sys
input = lambda : sys.stdin.readline().strip()

n,m=map(int,input().split())
li=[[]*m for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    li[a].append(b)
    li[b].append(a)

def dfs(node,d):
    print(ch)
    global r
    ch[node]=0

    if d >= 4:
        r = 1
        return

    for i in li[node]:
        if ch[i] == -1:
            dfs(i,d+1)
            ch[i]= -1

r=0
ch=[-1]*n
for i in range(n):
    dfs(i,0)
    ch[i]=-1
    if r == 1:
        break

print(r)

친구관계가 존재하는지 안하는지는 5명의 친구가 순서대로 친구관계를 이루는지를 통해 확인할 수 있습니다.

dfs를 이용해 한 친구를 기준으로 길이가 4까지 갈 수 있는지 확인했습니다.

백준 알고리즘 13023번 : www.acmicpc.net/problem/13023