글 읽기 - Floyd Warshall을 사용한 풀이

ili0820 2년 전 0

floyd warshall 돌리고 그냥 func을 통해서 대칭되는 부분, 즉 cycle이 있는지 확인 하는데 실패합니다.

0	1	1
1	0	1
0	0	0

이면 graph[0][1] graph[1][0]이 cycle을 만들기 때문에 cycle 이 존재

0	1	1
0	0	1
0	0	0

이면 no cycle

import sys

input=sys.stdin.readline
INF=int(1e9)

n=int(input())

graph=[[INF]*(n) for _ in range(n)]


for _ in range(n-1):
    k=int(input())
    temp=list(map(int,input().split()))

    for __ in range(k):

        graph[_][temp[__]-1] = 1


for a in range(n-1):
    graph[a][a]=0

for k in range(n):
    for a in range(n):
        for b in range(n):
            graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])



def func(n,graph):
    for a in range(n):
            for b in range(n):
                if  (0<graph[a][b]<INF) and (0<graph[b][a]<INF):
                    return 1
    return 0

print("CYCLE" if func(n,graph) else "NO CYCLE")

kth990303 2년 전 4

이 문제가 지문이 참 헷갈리는데,

중간에 cycle이 존재하더라도, 1번 노드에서 갈 수 없는 cycle인 경우는 cycle로 포함하지 않고 생각해줘야 AC를 받습니다.

도움이 될만한 test case를 첨부해드릴게요.

5
1
2
1
5
1
4
2
3 5
ans: NO CYCLE
wrong: CYCLE

ili0820 2년 전 0

엄..

if 0<graph[0][b]<INF:

한 줄 추가해서 1에서 갈 수 있는지 검사를 추가 했는데 그래도 56%에서 실패 합니다 ㅜㅜ

def func(n,graph):
    for a in range(n):
            for b in range(n):
                if 0<graph[0][b]<INF:
                    if  (0<graph[a][b]<INF) and (0<graph[b][a]<INF):
                        return 1
    return 0

kth990303 2년 전 0

뒤늦게 발견했네요

20번째 줄을 한번 잘 보시겠어요?

ili0820 2년 전 0

오.. 없애니까 통과는 하는데 저게 왜 문제가 되는지 잘 모르겠습니다.. graph[a][b] 와 graph[b][a]가 존재하는지 를 비교하는게 잘못 된 방식이고 graph[a][a]가 존재 하는 지를 보는 게 맞는거여서 그런걸까요?

kth990303 2년 전 2

사이클이 존재한다면 자기 자신으로 돌아오는 길이 존재할 것입니다.

따라서 graph[a][a]만 체크해주면 되긴 합니다만, 질문자님처럼 이중for문으로 체크해줘도 상관없습니다. Graph[a][b], graph[b][a] 둘 다 inf가 아니라는 것은 결국 graph[a][a]가 inf가 아니라는 것이기 때문이에요.

질문자님의 처음 코드가 틀렸던 이유는 graph[i][i]를 0으로 초기화시켜버렸기 때문에 플로이드 코드에서 의도치 않은 현상이 발생하기 때문입니다

ili0820 2년 전 0

넵 ㅜㅠ 책을 보고 하는데 책에서는 그냥 graph[i][i]를 0으로 초기화 시키고 시작하더라구요.. 항상 그러는게 옳진 않다는 것을 잘 배우고갑니다!!! 감사합니다!!!

kth990303 2년 전 2

대부분의 문제에선 i번째 노드에서 i번째 노드까진 원래 이동하지 않고도 도달가능하기 때문에 0으로 초기화하는게 맞아요.

다만 이 문제는 도달불가능할 경우 inf로 잡으셨기 때문에 사이클이 존재하지 않는 한 graph[i][i]는 inf로 두는 게 맞습니다.

늦은 밤까지 수고 많으셨어요 ㅎㅎ 화이팅입니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Floyd Warshall을 사용한 풀이

ili0820 2년 전 0

kth990303 2년 전 4

ili0820 2년 전 0

kth990303 2년 전 0

ili0820 2년 전 0

kth990303 2년 전 2

ili0820 2년 전 0

kth990303 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말