2162번 - 선분 그룹
하나의 선분을 하나의 노드로 생각하고,
두 선분이 교차하는 것은 두 노드가 연결되었다고 볼 수 있습니다.
선분의 개수가 3000개이므로 많은 편이니 인접 리스트로 선언하고,
그 다음 두 선분이 교차할 때 두 선분을 두 노드로 변환하여 그래프에 저장한 뒤,
bfs로 연결 요소의 개수, 그리고 가장 크기가 큰 연결 요소의 노드의 개수로 구하면 이 문제는 해결됩니다.
선분 교차 문제를 그래프 이론 문제로 변환하는 발상으로 이 문제를 해결했습니다.
덕분에 저는 이 문제를 한방에 맞췄습니다!
댓글을 작성하려면 로그인해야 합니다.
kjk9704 1년 전 2
하나의 선분을 하나의 노드로 생각하고,
두 선분이 교차하는 것은 두 노드가 연결되었다고 볼 수 있습니다.
선분의 개수가 3000개이므로 많은 편이니 인접 리스트로 선언하고,
그 다음 두 선분이 교차할 때 두 선분을 두 노드로 변환하여 그래프에 저장한 뒤,
bfs로 연결 요소의 개수, 그리고 가장 크기가 큰 연결 요소의 노드의 개수로 구하면 이 문제는 해결됩니다.
선분 교차 문제를 그래프 이론 문제로 변환하는 발상으로 이 문제를 해결했습니다.
덕분에 저는 이 문제를 한방에 맞췄습니다!