kjk9704   1년 전

하나의 선분을 하나의 노드로 생각하고,

두 선분이 교차하는 것은 두 노드가 연결되었다고 볼 수 있습니다.

선분의 개수가 3000개이므로 많은 편이니 인접 리스트로 선언하고, 

그 다음 두 선분이 교차할 때 두 선분을 두 노드로 변환하여 그래프에 저장한 뒤, 

bfs로 연결 요소의 개수, 그리고 가장 크기가 큰 연결 요소의 노드의 개수로 구하면 이 문제는 해결됩니다.

선분 교차 문제를 그래프 이론 문제로 변환하는 발상으로 이 문제를 해결했습니다.

덕분에 저는 이 문제를 한방에 맞췄습니다!

zenith82114   1년 전

연결 요소에만 관심이 있기 때문에 유니온 파인드로도 가능합니다.

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