[BOJ] 백준 15970번 : 화살표 그리기 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/15970

15970번: 화살표 그리기

문제

직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(<그림 1>). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. <그림 1>에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다.

<그림 1>

각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표시한다.

각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다.

모든 점에 대해서 같은 색깔을 가진 다른 점이 항상 존재한다. 따라서 각 점 p에서 시작하여 위 조건을 만족하는 q로 가는 하나의 화살표를 항상 그릴 수 있다.

예를 들어, 점들을 순서쌍 (위치, 색깔) 로 표시할 때, a = (0,1), b = (1, 2), c = (3, 1), d = (4, 2), e = (5, 1)라고 하자. 

아래 <그림 2>에서 이 점들을 표시한다. 여기서 흰색은 1, 검은색은 2에 해당된다.

<그림 2>

위의 조건으로 화살표를 그리면, 아래 <그림 3>과 같이 점 a의 화살표는 c로 연결된다. 점 b와 d의 화살표는 각각 d와 b로 연결된다. 또한 점 c와 e의 화살표는 각각 e와 c로 연결된다. 따라서 모든 화살표들의 길이 합은 3 + 3 + 2 + 3 + 2 = 13이다.

<그림 3>

점들의 위치와 색깔이 주어질 때, 모든 점에서 시작하는 화살표들의 길이 합을 출력하는 프로그램을 작성하시오.

 

풀이

브루트포스와 정렬을 사용하여 풀 수 있는 문제였습니다. 문제의 길이나 그림을 보면 조금 어렵게 느껴지실 수도 있지만, 차근 차근 이해하면 어렵지 않았다고 생각합니다.

이 문제에서 핵심은 같은 색깔끼리 좌표를 묶어주고, 오름차순을 하는 것이었습니다! 저는 인접리스트를 만들어서 각 색깔마다 좌표 배열을 생성하였습니다. 그리고 같은 색깔 내에 있는 좌표끼리 서로 거리를 구해주면 됩니다.

단, 처음과 끝 좌표는 비교 대상이 하나지만, 중간에 있는 좌표는 비교 대상이 앞과 뒤로 2가지이므로 더 짧은 거리를 구해야했습니다.

위 로직을 기반으로 아래와 같이 소스코드를 작성하시면 됩니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            a.add(new ArrayList<>());
        }
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int point = Integer.parseInt(st.nextToken());
            int color = Integer.parseInt(st.nextToken());
 
            a.get(color).add(point);
        }
 
        // color가 있는 칸마다 오름차순 정렬.
        for (int i = 0; i <= N; i++) {
            Collections.sort(a.get(i));
        }
 
        int ans = 0;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j < a.get(i).size(); j++) {
                if (j == 0) { // 맨 처음
                    ans += a.get(i).get(j + 1) - a.get(i).get(j);
                } else if (j == a.get(i).size() - 1) { // 맨 끝
                    ans += a.get(i).get(j) - a.get(i).get(j - 1);
                } else { // 중간
                    int t = a.get(i).get(j + 1) - a.get(i).get(j);
                    int f = a.get(i).get(j) - a.get(i).get(j - 1);
 
                    ans += Math.min(t, f);
                }
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.