목록vector (1)

맛있는감귤

BOJ : 2146 다리 만들기

문제 : https://www.acmicpc.net/problem/2146제가 푼 방식에는 두 가지 핵심이 있습니다.먼저 각 섬의 모서리 부분을 찾고 각 모서리가 어느 섬의 것인지 구분하기 위한 라벨링 작업두 번째는 각 섬에 대한 모서리 간의 거리 비교입니다. 라벨링은 DFS로 돌면서 근처에 물이 있으면 vector에 삽입했습니다. 한 지점에서 주위에 물이 두 군데 이상이면 중복 삽입되기 때문에 flag를 이용해 제외시켜주었습니다. 거리 비교는 BFS로 하려다가 굳이 그럴 필요가 없을 것 같아 서로 다른 라벨을 가지고 있는 섬끼리 비교하며 그냥 좌표를 빼줬습니다. #include #include using namespace std; int map[102][102], no=2, N, ans=98765432..
알고리즘/백준 알고리즘 2017. 3. 3. 15:34
이전 Prev 1 Next 다음