[백준] 2170번 선 긋기 (JAVA)

문제

- 매우 큰 도화지에 자를 대고 선을 그음

- 자의 한 점에서 다른 한 점까지 그음

- 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳은 한 번 그은 곳의 차이를 구별할 수 없음

- 그려진 선(들)의 총 길이를 구하는 프로그램 작성

 

해결방법

주어진 점들을 x(출발점)가 작은 순으로 정렬을 해준다. (이때, x가 같다면 y가 작은 순으로 정렬할 수 있도록 했다.) 모든 점들의 리스트에서 한 선씩 받아오는데 이전에 그었던 선의 범위 안에 속하면 계산하지 않고, 범위에 속하면서 더 그을 수 있으면 더 그은 부분만을 계산해주고 아예 범위를 벗어나서 선을 그은 부분은 그 길이만큼 계산할 수 있도록 코드를 구성하였다. 처음에 범위를 제대로 특정하지 않고 이전 y값과 비교하면서 길이를 더해주도록 코드를 작성하였는데 변수가 생겨 틀렸습니다를 몇번이나 마주했다.. 다시 제대로된 범위를 설정하고 비교하여 선을 그을 수 있도록 코드를 작성하니 7번 만에 성공을 확인할 수 있었다..

 

코드

import java.io.*;
import java.util.*;

// 입력받은 점들을 저장하기 위한 Point 클래스
class Point implements Comparable<Point>{
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // x에 따라 오름차순 정렬하고 같은 경우 y에 따라 오름차순으로 정렬
    @Override
    public int compareTo(Point o) {
        if(this.x == o.x) return this.y - o.y;
        else return this.x - o.x;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int before = 0, ans = 0;
        List<Point> points = new ArrayList<>();		// 입력된 점들을 저장하는 리스트

        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points.add(new Point(x, y));
        }

	// Point 클래스에서 정의한 기준에 따라 리스트를 정렬
        Collections.sort(points);

	// 처음 그은 선
        int x = points.get(0).x;
        int y = points.get(0).y;
        ans += y - x;
		
        // 다음 선부터는 기준에 따라 길이를 더해줄 수 있도록 구성
        for(int i = 1; i<points.size(); i++){
            int nx = points.get(i).x;
            int ny = points.get(i).y;

	    // 이전에 그은 선의 범위 내에 속할 때
            if((x <= nx) && (ny <= y)) continue;
            // 이전에 그은 선의 범위 내에 속하면서 더 선을 그을 때
            else if(nx < y) ans += ny - y;
            // 이전에 그은 선의 범위를 벗어나 선을 그을 때
            else ans += ny - nx;

            x = nx;
            y = ny;
        }
	// 총 그은 선의 길이 출력
        System.out.println(ans);
    }
}