13023

날짜 : 2023. 03. 20

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, sys.stdin.readline().split())  # 사람의 수, 관계의 수
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)  # 두 노드 연결
    graph[b].append(a)


def dfs(now, depth):
    visited[now] = True  # 노드 방문처리
    if depth == 5:
        print(1)  # 조건 만족 시 1 출력
        exit()
    for i in graph[now]:
        if not visited[i]:  # 방문하지 않았다면
            dfs(i, depth + 1)  # 재귀
            visited[i] = False  # 탐색 실패 -> 미방문 처리
    return


for i in range(n):
    if len(graph[i]) > 0:
        visited = [False] * n
        dfs(i, 1)
print(0)

 

 

풀이

- 전체 그래프에서 A, B, C, D, E가 서로 연결되어 있는 그래프를 찾는 것이다. 즉, 깊이가 4인 그래프를 찾는 문제였다.

- 그래서 각 노드별로 DFS를 수행하고, 조건에 맞는 경우 1을 출력한 후 프로그램을 끝내는 방식으로 코드를 작성한다.

- 다만, 탐색에 실패한 경우 다른 경우의 수를 찾아야 하기 때문에 dfs에서 탈출한 경우 해당 노드에 대해서는 방문처리를 False로 바꿈으로써 다른 경우의 수로 방문할 수 있도록 처리한다.

 

 

알게된 점

- DFS를 수행할 때 탐색을 실패한 케이스를 고려하지 못하고 코드를 작성해서 틀렸다.

반례

0 1
1 3
1 4
4 3
3 2

-> output : 1

 

참고 사이트

-