화살표 그리기( BOJ 15970 - 초등 )

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

15970번: 화살표 그리기

 

문제 파악하기

N개의 점을 가장 인접한 같은 색깔 점과 연결하여 만든 화살표 길이의 합을 구하는 문제입니다. 점은 항상 같은 색깔인 점과 연결할 수 있으며, 가장 인접한 점을 찾아 그 사이의 길이를 구해야 합니다. 이 문제의 경우, N의 크기가 최대 5,000이하로 주어지기 때문에 가장 단순한 방법인 완전탐색을 통해 문제를 해결할 수 있습니다.

 

문제 해결하기

하나의 점 마다 좌표와 색깔이 주어지므로 2차원 배열을 사용해도 되고, 구조체를 만들어 저장해도 되고, pair< >형을 사용해도 됩니다. 이렇게 값을 저장한 후에는 N개의 점에 대해 중첩 반복문을 만들어 가장 가까운 점의 위치를 구하고 그만큼 거리를 더해주면 문제를 해결할 수 있습니다. 다만, N의 값이 점점 커진다면 위 알고리즘은 사용하기 어려워진다는 단점이 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#define INF 0x7FFFFFFF
#define PAIR pair<int,int>
using namespace std;
 
int N, p, c;
vector< PAIR > inp;
 
int tmp, ret;
 
int abs(int k) { return k>0 ? k:-k; }
 
int main() {
    // input
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%d %d", &p, &c);
        inp.push_back({p, c});
    }
 
    // search
    for(int i=0;i<N;i++) {
        tmp = INF;
        for(int j=0;j<N;j++) {
            if(i!=j and inp[i].second == inp[j].second) {
                tmp = min( tmp, abs(inp[j].first-inp[i].first) );
            }
        }
 
        if(tmp != INF) ret + = tmp;
    }
 
    // print
    printf("%d", ret);
}

후기

중첩 반복문을 사용하는 연습을 할 수 있는 문제라고 생각합니다. 최댓값/최솟값 구하는 알고리즘을 배운 다음에 풀어볼만한 문제로 추천하고 싶습니다.