[백준][13023] ABCDE

• Problem Link : https://www.acmicpc.net/problem/13023

문제

A, B, C, D, E가 인접한 친구와 친구 관계인 경우가 존재하는지 안하는지를 구하여라.

입력

• 첫째 줄, N, M이 주어진다.
• 둘째 줄, 정수 a, b가 m개 주어진다. a와 b가 친구라는 뜻이다.

출력

• A, B, C, D, E가 존재하면 1, 없으면 0을 출력한다.

풀이

단순한 그래프 탐색 문제, 연속된 노드 5개를 찾으면 1, 아니면 0을 출력하는 문제이다. 시간 단축을 위해 DFS와 백트래킹 기법을 쓰면서 DFS에서 다음 노드로 진행할 때마다 깊이가 1 증가하고 깊이가 5가 된다면, 이어진 노드가 5개가 있다는 뜻이므로 문제에서 원하는 A, B, C, D, E가 존재하는 것을 의미한다.

만약 실행 중에 깊이 5를 발견한다면 우리가 원하는 친구 관계를 찾았음을 의미하고 추가적인 탐색은 의미가 없으므로 1을 출력후 프로그램을 종료하도록 설계했다.

코드

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline


# dfs algorithm
def dfs(graph, v, visited, depth):
    if depth == 5:
        print(1)
        exit()

    for i in graph[v]:
        if not visited[i]:
            visited[v] = True
            dfs(graph, i, visited, depth + 1)
            visited[v] = False
    return


# input
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# solution
for i in range(n):
    visited = [False] * n
    if not visited[i]:
        dfs(graph, i, visited, 1)

print(0)