체인점( BOJ 2472 )

문제

2472. 체인점 : https://www.acmicpc.net/problem/2472

2472번: 체인점

 

문제 파악하기

• 아파트는 A, B, C로 총 3개의 노드가 주어집니다.
• 후보지 p에서 A, B, C까지의 거리가 후보지 q에서 A, B, C까지의 거리보다 모두 먼 경우, 후보지 p에는 매장을 설치하지 않습니다.
• 후보지에 매장을 설치할 수 있는지 여부를 알기 위해서는 후보지마다 A, B, C까지의 거리를 구해야 합니다. 
• 거리는 음수가 나오지 않기에 가장 빠른 다익스트라 알고리즘을 3번 사용하면 됩니다.
• 후보지에 매장을 설치할 수 있는지 여부는 자신보다 모든 거리가 가까운 매장의 존재 여부를 구하면 됩니다.
• 이 경우, 세그먼트 트리를 사용하면 해결할 수 있습니다.

 

문제 해결하기

• 세그먼트 트리를 사용하기 위해서는 우선 A, B, C까지의 거리를 기준으로 정렬해야 합니다.
• 그리고 A까지의 거리 순서대로 세그먼트 트리를 만들어줍니다.
  세그먼트 트리에 들어갈 위치는 정렬된 B까지의 거리에서의 노드 위치입니다.
• 이렇게 세그먼트 트리를 구성하면 나보다 왼쪽에 저장된 노드들은 나보다 A와 B까지의 거리가 같거나 더 짧은 노드입니다.
• 여기서 C까지의 거리를 세그먼트 트리에 저장하면 A, B, C까지의 거리를 한번에 확인할 수 있습니다.
• 다만, 거리의 값이 커질 수 있기에 값을 압축해서 계산하는걸 추천합니다.
• 세그먼트 트리 구성이 어렵다면 굉장한 학생 문제를 먼저 풀어보는걸 추천합니다.

 

후기

문제 이해는 쉽지만 구현이 어려운 문제라고 생각합니다. 세그먼트 트리의 매력을 느낄 수 있는 어려운 문제라고 생각합니다.