[백준 11581] 구호물자 (Python)

문제

 

이 문제는 플로이드 워셜로 분류된 문제이다.

 

문제를 푸는 과정은

1. 플로이드 워셜 알고리즘을 이용해 모든 경로 저장

2. CIRCLE이 생기는 경우가 언제인지

3. CIRCLE이 생기지만 1의 경로에 포함되는지 여부

 

위의 과정중에 3번을 고려하지 않아 제출했을때 52%에서 계속 실패가 떴다..

 

내 코드

n = int(input())

m = 0
arr = [[0 for col in range(n)] for row in range(n)]
for i in range(n-1):
    m = int(input())
    node = map(int, input().split())
    for j in node:
        arr[i][j-1] = 1


for k in range(n):
    for i in range(n):
        for j in range(n):
            if arr[i][k] and arr[k][j]:
                arr[i][j] = 1

for i in range(n):
    if arr[i][i] ==1 and arr[0][i]: 
        print('CYCLE')
        exit()
print('NO CYCLE')

CIRCLE이 생기는 경우는 arr[i][i]인 경우다.

CIRCLE은 교차로를 다시 방문하는 경우이기 때문에 결국 순환이 생겨서 자기자신을 방문할 수 있는 경로가 생기는 경우라고 볼 수 있기 때문이다.

 

 

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

11581번: 구호물자