[삼성] 17779 게리멘더링 2

삼성전자 기출문제로, 경계선에 따라 구역을 나눌 수 있느냐를 물어보고 있다.

 

1. 모든 점들을 기준점으로 탐색한다 O(N^2)

2. 기준점을 기준으로 경계선의 꼭짓점이 맵 안에 존재하는지 확인한다 O(N^2)

3. 경계선이 성립이 된다면 그 구간을 그룹 5로 초기화한다 O(N)

4. 지도의 각 끝점에서 bfs를 돌리면서 구간선까지 탐색을 한다 O(N^2)

5. 최솟값을 구한다 O(상수)

 

위 시간복잡도는 나올 수 없다. 다만 계산을 편하게 하기 위해 다음과 같이 설정했고, 총 시간복잡도는

O = O(N^2)*O(N^2)*(O(N)+O(N^2)+O(상수)) = O(N^6)

N제한이 20이므로 1억 이하므로 해결할 수 있다

 

문제: https://www.acmicpc.net/problem/17779

깃허브주소: https://github.com/surinoel/boj/blob/master/17779.cpp