[백준] No.17619 - 개구리 점프 (C++)

문제

 

www.acmicpc.net/problem/17619

17619번: 개구리 점프

 

풀이

 

solved.ac 난이도: Gold 3

 

정렬과 분리 집합(Disjoint set)으로 해결하는 문제이다. 

이번 문제의 분리 집합의 구현에 사용하는 Union-Find(유니온-파인드) 자료구조에 대해서는 아래 게시글에 정리해두었다.

유니온-파인드(Union-Find), 분리 집합

 

이번 문제에서는 점프로 이동 가능한 통나무들을 한 집합으로 묶어 서로 이동 가능한지 판별하려 한다.

점프로 이동 가능하기 위해서는 통나무 수평선의 x좌표가 겹쳐한다. x좌표가 겹치지 않고 서로 떨어져 있다면 해당 통나무들은 서로 이동이 불가능하다.

 

일단 통나무의 x1(left) , x2(right), y, 번호를 저장하기 위한 구조체를 선언하자.

 

class Log{
  public:
  int left,right, y, num;
  Log() {}
  Log(int x1,int x2, int _y,int n) :left(x1),right(x2), y(_y), num(n){}
};

 

이제 통나무들의 정보를 모두 입력받고 다음과 같은 순서로 통나무들을 통나무의 오른쪽 x좌표인,

right에 대한 오름차순(큰 수가 앞)으로 정렬해야 한다.

만약 right좌표가 같다면 left에 대해 내림차순(작은 수가 앞)으로 정렬해주자.

 

이를 위한 Compare함수는 아래와 같다.

 

bool Compare(Log &a, Log& b){
  if(a.right == b.right)
    return a.left< b.left;  //right가 같다면 내림차순
  return a.right > b.right; //right에 대한 오름차순
}

 

이와 같은 순서로 정렬하는 이유를 아래의 예제로 생각해보자.

 

 

이와 같은 통나무가 주어지면 결국 이동 가능하므로 같은 집합에 속하게 된다.

 

하지만 위에서부터 순서대로 집합의 합치기 과정(Union)을 하게 된다면 

위의 두 통나무는 x좌표가 겹치므로  하나의 집합을, 다음의 통나무와는 겹치지 않아 집합이 분리된다.

결국에는 마지막 통나무와 모두 x좌표가 겹치므로 위와 같은 순서대로 정렬하면

 

위(배열에서는 앞)의 통나무의 right는 항상 다음 통나무들보다는 크거나 같다.

따라서 이번 통나무의 left가 다음 통나무의 right보다 작다면 두 통나무는 겹친다는 것을 알 수 있다.

이런 경우에만 서로 Union을 해주자.

 

만약 다음 통나무와 겹치지 않는다면(다음 통나무의 right가 left보다 작다면) 뒤의 모든 통나무와도 겹치지 않으므로 집합을 분리해주자.

(단순히 Union을 해주지 않으면 된다.)

 

DisjointSet set(log_num);
int next_idx;
int set_left= logs[1].left;
 
for(int idx=1; idx<log_num ; ++idx){
  next_idx = idx +1;
  if(set_left <= logs[next_idx].right)
    set.Union(logs[idx].num, logs[next_idx].num);
    
  set_left = min(set_left,logs[next_idx].left);
}

 

이때 같은 집합의 통나무들은 서로 넘어 다닐 수 있으므로 해당 집합에서 가장 left가 작은 값을 set_left로 설정하여 다음 통나무들을 차례대로 순회하자.

이렇게 특정 순서로 정렬을 해준 후 차례대로 순회하여 답을 낼 수 있는 기법을 스위핑 기법이라고 한다.

 

최종적으로 두 통나무의 번호를 입력받아 Find함수를 통해 두 통나무가 같은 집합에 속하는지 확인하면 된다.

 

 

코드