문제 조건 관련 질문

Question

문제( https://www.acmicpc.net/problem/1260 )에 다음과 같은 조건이 있는데, 이게 무슨 의미인가요..? 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.

개발자로 취직하기 · Answer

도토리님 안녕하세요 :) 이 말은 간선 정보가 주어질 때 중복으로 정보가 들어올 수 있다는 겁니다. 지금 예시에는 그런 내용이 없지만 예를 들어 [1, 2] 라고 들어오면 1번과 2번이 연결되었다는 건데 그 다음에 [2, 1]이 들어올수도 있는 거고, 아니면 [1, 2]가 또 들어올 수도 있다는 의미입니다. 아마 출제자가 주고자 했던 정보는 "간선 중에 중복이 있으니 잘 처리하는지 볼거다"라는 것으로 추정돼요. 가장 극단적으로는 [1,2]라는 정보만 100번 들어왔는데, 중복처리를 하지 않으면 100개의 간선을 다 확인하느라 시간 초과가 발생할 수도 있습니다. 저희가 강의 때 작성한 코드에서는 애초에 graph 자료구조에 통합하는 방식을 써서 100개의 중복 정보가 들어와도 그냥 같은 위치가 100번 True로 set될 뿐, 실제 처리할 때는 한 점으로 확인하기 때문에 문제가 없는 거고, 그래서 아마 왜 이런 정보가 주어졌는지 궁금해 하셨을 것 같아요! 한줄로 요약하면 "중복처리 잘해라!" 라는 의도의 문구였습니다. 또 궁금하신 점 있거나 설명이 부족했으면 질문 남겨주세요!