백준 15970. 화살표 그리기

화살표 그리기

간단한 정렬 문제

1. 간단 설명

---

어떤 좌표에 색상이 주어진다

이 색상과 같은 좌표를 연결하면 화살표가 되는데, 그 화살표 길이들의 합이 최소값을 구하는 문제

문제가 길어서 그렇지 잘 읽으면 쉬움

2. 예제

---

예제 1)

5
0 1
1 2
3 1
4 2
5 1

점 5개 [0, 3, 5]는 1번 색상, [1,4]는 2번 색상을 가진다

점 0의 선 길이 : 0-3 = 3 점 1의 선 길이 : 1-4 = 3 점 3의 선 길이 : 3-5 = 2 점 4의 선 길이 : 4-1 = 3 점 5의 선 길이 : 5-3 = 2

총 길이의 합은 13

예제 2)

7
6 1
7 2
9 1
10 2
0 1
3 1
4 1

점 7개 [0,3,4,6,9] 는 1번 색상, [7,10]은 2번 색상

1번 색상의 선부터 구하면

점 0의 선 길이 :	0-3	= 3
점 3의 선 길이 : min(	3-0	,	3-4	) = 1
점 4의 선 길이 : min(	4-3	,	4-6	) = 1
점 6의 선 길이 : min(	4-6	,	6-9	) = 2
점 9의 선 길이 :	6-9	= 3

점 7의 선 길이 :	7-10	= 3
점 10의 선 길이 :	10-7	= 3

총 길이 16 이 된다

3. 알고리즘

---

각 좌표는 특정한 색상을 가진다

같은 색상을 가진 좌표들만 연결할 수 있으므로, 같은 색상들끼리 묶어서 관리한다

이를 위해 MAP 자료구조를 사용하면 편하다

1. N 입력받기
2. {좌표, 색상} 쌍을 입력받으면서, 색상을 키로 갖는 Map을 생성한다
	2-1. 색상이 이미 존재하면 뒤에 계속 추가해준다
3. 기록된 색상별로 화살표 길이를 구한다
	3-1. 먼저 좌표를 오름차순으로 정렬한다 
	3-2. 0번 좌표라면 1번 좌표까지의 길이 구하기
	3-3. 마지막 좌표라면, 마지막 좌표 - 1번까지 길이 구하기
	3-4. 그 외 경우, 왼쪽과 오른쪽을 비교하여 최소값을 구한다
	3-5. 구한 값을 전체 화살표 길이에 더한다
4. 화살표 길이 출력 후 종료

필요 변수

• int N : 전체 점들의 개수
• map<int, vector<int>> points : 점의 색상을 키로, 좌표를 벡터로 저장하는 map
• long long total_dis : 전체 길이

4. 소스코드

---

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int N;
map<int, vector<int>> points;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		int pos, color;
		cin >> pos >> color;
		points[color].push_back(pos);
	}


	// 거리 계산
	long long total_dis = 0;

	for (const auto &e : points) { // 주소 참조
		vector<int> pos = e.second; // 복사 

		sort(pos.begin(), pos.end());

		for (int i = 0; i < pos.size(); i++) {
			
			if (i == 0) {
				total_dis += abs(pos[0] - pos[1]);
			}
			else if (i == pos.size() - 1) {
				total_dis += abs(pos[pos.size() - 1] - pos[pos.size() - 2]);
			}
			else {
				total_dis += min(abs(pos[i - 1] - pos[i]), abs(pos[i] - pos[i + 1]));
			}
		}
	}

	cout << total_dis;

	return 0;
}

MAP을 사용하여 쉽게 해결할 수 있었던 문제