ckdtjs505   2년 전

왜틀렸을까요? .....

최소의 경우 최대의 경우 다 따져봤는데도 잘 모르겠습니다ㅠ

ckdgus2482   2년 전

양방향 그래프입니다

ckdtjs505   2년 전

ckdgus2482..

양방향 그래프로 구현해서 제출했는데.. 맞았다고 제출이 되었습니다.

하지만 여전히 저는 이해가 되지 않습니다. 

왜 단방향 그래프는 틀렸는지..


저의 생각은 이렇습니다. 

굳이 양방향을 할필요가 있는가?

탐색하는 방향은 정해져있지 않은가?

혹시나 반례를 알려주신다면 더욱 감사합니다

꾸벅

ckdgus2482   2년 전

출발점이 고정이라고 해서 탐색하는 방향이 정해져있는것은 아닙니다.

각각의 간선을 따라갈때 항상 같은 방향으로만 따라간다면 단방향 그래프로 봐도 되겠지만 이 문제는 그렇지 않습니다.

간단한 예를 들자면

3

2

2 1

3 2

이러한 입력에서 올바른 답은 2이지만

단방향 그래프로 탐색한다면 0이겠죠

mjkim1201   1년 전

근데 문제에 a<b라는 조건이있는데 그럼 2 1 자체가 입력이 안되지 않나요 ?

yeolpyeong   1년 전

10
10
4 10
7 10
3 7
6 8
1 7
1 6
1 5
1 9
2 4
3 8

단방향 그래프는 이런 경우 3번(친구의 친구)을 카운트할 수 없습니다.

1 -> 7 -> 3

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