백준 13023 ABCDE

import sys

n,m=map(int,sys.stdin.readline().split())
friend=[list() for i in range(n)]

for _ in range(m):
    start,end=map(int,sys.stdin.readline().split())
    friend[start].append(end)
    friend[end].append(start)

def DFS_recur(first,idx):

    visited[first]=1

    if idx==4:
        print(1)
        exit()

    for i in friend[first]:
        if visited[i]==0:
            DFS_recur(i,idx+1)
            visited[i]=0

for i in range(n):
    visited = [0 for i in range(n)]
    DFS_recur(i,0)
print(0)

이 문제도 기본적인 그래프 문제 유형이라 생각한다.

A가 B를 알고 B가 C를 알고 C 가 D를 알고 D가 E를 아는 친구 관계가 있을떄

A-B-C-D-E 가 되는 관계가 있나 없나를 판단하는 문제이다.

​

나는 간단하게 DFS의 깊이가 4,5(시작이 1이면) 이 된다면 1를 출력하게 구현했다.

그리고 만약 0에서 시작했을때 모든 0에서 시작한 모든 방향들을 봐야하기에 그리고 그 방향이 실패했을 경우 다시 그 정점을 다른 정점에서 방문해야하기에 그 방향이 실패했을경우 돌아왔을땐 원래상태로 돌려줘야한다.

나는 이걸 백트래킹이라 생각한다.

뭐 하여튼 그래서 백트래킹으로 DFS 함수를 재귀적으로 돌림과 동시에 바로 밑에 다시 원래대로 돌려주는 코드를 한번더 작성했다.

Ez