tmdgns12j   2년 전

도대체 어디서틀리는걸까요ㅜㅜㅜ

링크가0일때도 문제는없는데..

djm03178   2년 전

간선이 양방향이기 때문에 입력된 간선 정보를 그대로 sort 하면 원하는 결과가 나오지 않을 수 있습니다.

예를 들어,

2 3

3 1

과 같은 간선이 두 개 들어왔다면 3에서 방문을 시작했을 때 먼저 방문해야 할 정점은 1이겠지만 sort에서 이 순서를 2 3, 3 1로 유지하기 때문에 new[3]에 추가되는 순서가 2, 1이 되어 탐색 시에 2를 1보다 먼저 탐색하게 됩니다.

tmdgns12j   2년 전

ㅇ0ㅇ 그런문제가있었군여

정말루 감사합니다ㅜㅜ

그러면 이런류의 문제를풀때 정렬하여푸는건 그닥 좋지않은 방법일까요?

djm03178   2년 전

좋지 않을 이유는 없는 것 같습니다. 문제 자체가 정렬을 하게끔 요구하고 있으니 의도대로의 정렬만 해주면 됩니다.

tmdgns12j   2년 전

preview

이렇게 30번째줄-arr.sort()를 밖으로빼면 정상적으로 정렬이되고 문제에있는 테스트케이스도 만족하게됩니다

이것도 틀렸다고 나오는데 어디가문제일까요..

djm03178   2년 전

그림으로 올려주시면 제가 테스트해보기가 힘듭니다...

그리고 정렬의 위치에 관계 없이 제대로 안 될 거라고 생각되네요. [2,3]은 [3,1]보다 작습니다.

tmdgns12j   2년 전

아 ㅁㅊㅁㅊㅁㅊ 그렇네요.. 이제야 제대로 이해했습니다..

결국 new에 [1,2] 이런식으로 정렬이 되어야 한다는 말씀이신거같은데 제가 이해한게 맞나 모르겠습니다..

이게 맞다면 리스트 안의 내용물을 정렬해야하는데.. 어떤방법이있을까요ㅜ

sort()를쓰면 2차원 배열이다보니 전체적인 순서만 변경되는거 같더군요..

djm03178   2년 전

정렬을 해야 하는 대상이 무엇일지 잘 생각해 보세요. 중요한 건 각 정점에 대해서 거기에 연결된 리스트가 정렬되어 있으면 된다는 것입니다.

tmdgns12j   2년 전

와 방금 풀었습ㄴ디ㅏ 진짜 3일동안 고생했던건데 정말 감사합니다ㅜㅜㅜ

덕분에 새로운 방법 알아갑니다ㅜㅜㅜㅜ

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