[python] 백준 13023 ABCDE

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

13023번: ABCDE

 

문제 해결

bidirectical graph 가 4개가 연결되어있는 것이 하나라도 있으면 1을 출력하고 아니면 0을 출력

따라서 그래프가 이어지는 횟수가 4개가 되면 1을 출력하도록 하고 한번도 체크가 안되면 0을 출력하도록 하면 된다.

visited 리스트를 만들어 방문했던 곳은 중복으로 방문하지 않도록 한다.

 

CODE

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 0
def dfs(start, cnt):
    global ans
    visited[start] = True
    if cnt == 4:
        ans = 1
        return 1
    for next in graph[start]:
        if not visited[next]:
            visited[next] = True
            if dfs(next, cnt+1) == 1:
                return 1
            visited[next] = False
    return 0

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