[Python] BOJ 13023 - ABCDE

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

13023번: ABCDE

# 처음에 그냥 union-Find문제인 줄 알고 풀었는데 요구하는 바가 약간 달랐다.

   단순히 한 사람이 다른 몇명과 친구인지가 중요한게 아니라

   문제에서 요구하는 A-B, B-C, C-D, D-E 이 4가지의 경우를 만족하는지 확인하는 문제이다.

   따라서, DFS를 사용하여 꼬리에 꼬리를 무는 식으로 풀었다.

 

# DFS함수: cnt와 x를 넘겨받아 cnt가 4가 되면 문제에서 요구하는 친구관계가 성립되었으므로

                 1을 출력하고 프로그램을 종료한다.

  

                graph[x]안의 원소들을 돌면서 i원소를 방문하지 않았으면 방문처리를 하고

                  dfs(cnt+1, i) 를실행한다.

               dfs재귀의 끝까지 확인했는데 cnt가 4가 되지 않은 상태로 나왔다면

                   visited[i]를 False로 바꿔준다.

 

# M개의 친구관계를 graph에 저장하고 0부터 N-1까지 dfs(0, i)를 실행한다.

    dfs재귀의 끝까지 확인해서 cnt가 4가 아니라면 나와서 visited[i]를 False로 바꿔준다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, M = map(int,input().split())
graph = [[] for _ in range(N)]
visited = [False] * N

def dfs(cnt, x):
    if cnt == 4:
        print(1)
        sys.exit(0)

    for i in graph[x]:
        if not visited[i]:
            visited[i] = True
            dfs(cnt+1, i)
            visited[i] = False

for _ in range(M):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(N):
    visited[i] = True
    dfs(0, i)
    visited[i] = False
print(0)

(solved.ac 티어: 골드 5)