d252b   6년 전

문제가 어느 한 노드에서 시작해서 다른 노드로 갈 수 있느냐 , 그 노드의 갯수를 찾아보아라! 이런 문제인 것 같아

플로이드-워셜 알고리즘을 사용했습니다.

그러나 플로이드 워셜 알고리즘을 통해 나온 결과값에서 답으로 어떻게 도출해 내야 할지 모르겠습니다

먼저 제가 한 방식은

플로이드-워셜 알고리즘을 통해 나온 결과에서

예를 들어,  arr[4][3] = INF 일 경우, arr[3][4] 를 찾아봐서 INF가 아니라면 4와 3사이의 키를 비교 할 수 있다고 생각했습니다.

그러나 arr[4][3] = INF 이고, arr[3][4] 가 INF인 경우에는 서로 키를 비교 할 수 없다고 생각했고요.

아예 틀린 방향으로 생각하고 있는 건가요?;;

joonas   6년 전

flag가 1이란게, 비교할 수 없다라는 뜻인가요?

그럼 flag가 1인 것들의 수를 세면 비교할 수 없는 노드의 수를 세는 것 같네요.

joonas   6년 전

4 3
1 2
1 3
2 4

답은 1 입니다.

d252b   6년 전

아니요 flag==1 인 것들이 비교를 할 수 있다는 의미입니다.


그래서 if (flag==1) cnt++;

이렇게 되서 답은 cnt

즉, 자신의 키의 위치를 알 수 있는 노드가 몇 개 인지를 카운팅 하는 거에요.

joonas   6년 전

코드를 이해했습니다. 그럼 62번줄에서 찾지 못한 경우에 왜 break를 하는 지 알 수 있을까요?
flag == 1 일때, break하는 게 맞아보이네요

d252b   6년 전

if (1->2 == INF && 2->1== INF)

1과 2, 2와 1 모두 대소 비교를 할 수 없으므로 누가 크고 작은지 알수가 없다. 즉, 그럼 1번은 그 이후 사람들과 비교해도 이미 2번과 비교할 수 없으므로

바로 break 걸고 넘어간다는 의미였어요. 


아래에서

if(flag==1) 의 의미는 즉, 어떤 N과 1~M 에 대해 모두 크고 작음을 알 수 있다는 의미여서

cnt++ 즉, 답을 +1 해준거였습니다.. ㅠㅠ 

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