shinbian11   3년 전

dfs로 구현했고 맞았는데 궁금한 점잉 있습니다.

밑 코드처럼 입력받는 편의점의 좌표를 cmp함수를 커스터마이징해서 저렇게 구현하면 런타임에러가 나고, 안하면 정답처리가 되는데,

편의점 좌표를 정렬할 필요가 없는 이유가 뭔가요? 39번째 줄에 어짜피 방문한 편의점은 continue 해서 지나가기 때문인가요??

만약 그렇다면 sort 의 cmp를 이용하여 제 마음대로 정렬을 한 다음에 해도 정답처리가 되는건 매한가지라고 생각을 했는데,

cmp 를 하면 틀리고 안 하면 맞는 이유가 궁금합니다. 애초에 cmp함수 구현이 잘못된 건가요??

감사합니다.

evenharder   3년 전

작성하신 cmp 함수가 정렬 함수의 조건(strict weak ordering)을 만족하지 않아서 그렇습니다.

- a < a는 false

- a < b가 true이면 b < a는 false

- a < b가 true이고 b < c가 true이면 a < c도 true

- a < b, b < a, b < c, c < b가 전부 false면 a < c, c < a가 false

작성하신 함수로는 cmp((-1, -1), (-2, -2))랑 cmp((-2, -2), (-1, -1))가 둘 다 true가 나오기 때문에 조건을 만족하지 않습니다.

이렇게 조건이 맞지 않는 함수과 입력이 들어오면 런타임 에러가 발생합니다.


작성하신 DFS 함수는 만족하는 경로가 있으면 어떻게든 찾아내고, 존재하지 않으면 찾지 못합니다. 각 장소별로 갈 수 있는 모든 장소를 조사해보기 때문입니다.

shinbian11   3년 전

감사합니다. cmp 함수 구현에서 문제가 있었군요. 그럼 만약에 cmp 함수를 굳이 만들어서 써야겠다면 어떤 식으로 커스터마이징해야 할까요?

evenharder   3년 전

위의 조건을 만족하는 정렬 기준이면 괜찮습니다. 예시로는

- pair<int, int>의 기본 < 연산자 (a.first != b.first ? a.first < b.first : a.second < b.second)

- a.first + a.second < b.first + b.second (비슷하게 -도 됩니다)

- a.first < b.first (second를 무시하는 연산자)

https://koosaga.com/97 에 있는 각도 정렬

등 필요에 따라 다양하게 만들 수 있습니다. 조금 모호하지만 일반적인 < 함수의 역할을 하는지 확인해보시면 됩니다.

shinbian11   3년 전

고맙습니다!

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