[백준, Java] 2170번, 선 긋기 (그리드 알고리즘)

문제 링크

2170번: 선 긋기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 선을 그을 때는 이미 선이 있는 위치에 겹쳐서 그릴 수 있습니다.

2. 선이 여러 번 그어진 곳은 한 번씩만 계산한다.

3. 선의 총 길이를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 두 점의 위치를 기준으로 정렬한 뒤 선의 그어서 길이를 측정합니다.

 

3. 측정한 선의 길이를 결과로 출력합니다.

 

 

선을 긋는 과정

 

두 점의 위치를 기준으로 정렬하는 이유

 

모든 선이 이어지게 입력되지 않을 수 있습니다.

즉, 정렬을 통해 연결되는 인접한 선들을 탐색해서 연결되는지 확인합니다.

 

인접하였지만 연결되지 않으면 다음에 연결되는 선들은 이전에 존재하는 선들에 더 이상 연결되지 않습니다.

→ 이전의 선들은 길이가 정해지므로, 해당 선의 길이는 인접한 선이 연결되지 않으면 구해서 최종 결과값에 더합니다.

 

※ 저는 시작 위치를 기준으로 오름차순 정렬, 시작 위치가 같을 때 끝 위치 기준 내림차순 정렬하였습니다.

→ 반대로 정렬해도 문제를 푸는데에는 상관 없습니다.

 

과정.

 

1. 정렬된 선들 중에서 순차적으로 그리기 시작합니다.

2. 선을 그릴 때 시작 위치가 이전 마지막 위치보다 크면 연결되지 않는 선입니다.

3. 시작 위치가 마지막 위치보다 작거나 같으면 연결된 선입니다.

 

 

예제입력 1.

1. 입력된 정보를 저장합니다.

N : 4

 

1 3

 

2 5

 

3 5

 

6 7

2. 두 점의 위치를 기준으로 정렬한 뒤 선의 그어서 길이를 측정합니다.

 

두 점의 위치를 기준으로 정렬!

 

1	3
2	5
3	5
6	7

 

선 그리기!

시작 위치 : 1

끝 위치 : 3

→ 시작 위치(2)가 기존 선 끝 위치(3)보다 작으므로 연결될 수 있습니다.

시작 위치 : 1

끝 위치 : 5

→ 시작 위치(3)가 기존 선 끝 위치(5)보다 작으므로 연결될 수 있습니다.

시작 위치 : 1

끝 위치 : 5

 

→ 시작 위치(6)가 기존 선 끝 위치(5)보다 커서 선이 분리됩니다.

기존 선의 길이 (끝 위치 - 시작 위치) : 5 - 1 = 4

 

새로운 선의 정보

 

시작 위치 : 6

끝 위치 : 7

 

모든 선 긋기 종료!

 

마지막 선의 길이 구하기!

마지막 선의 길이(끝 위치 - 시작 위치) : 7 - 6  = 1

 

3. 측정한 선의 길이를 결과로 출력합니다.

 

 

모든 선의 길이 더하기 : 4 + 1 = 5

 

5을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 선의 시작위치와 끝위치를 저장합니다.
• PriorityQueue와 Inner Class:Info을 사용해서 선의 위치를 기준으로 정렬하였습니다.
• 반복 탐색을 통해 선을 긋기 과정을 진행하였습니다.
• 과정이 끝난 뒤 선의 길이를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    //선의 정보 저장하는 InnerClass
    static class Info implements Comparable<Info>{
        int x, y;	//x : 시작 위치, y : 끝 위치
        public Info(int x, int y){
            this.x = x;
            this.y = y;
        }

        //선의 정보 정렬 기준
        @Override
        public int compareTo( Info o) {
            if(this.x == o.x)	//시작 위치가 같을 때 끝 위치 내림차순
                return o.y - this.y;
            return this.x - o.x;	//시작 위치 다를 때 시작 위치 오름차순
        }
    }
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //선의 정보 기준 정렬되어 사용할 PriorityQueue
        PriorityQueue<Info> pq = new PriorityQueue<>();
        //입력되는 선의 정보 PriorityQueue 저장
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            pq.offer(new Info(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        Info first_line = pq.poll();
        //현재 선의 시작 위치
        int start = first_line.x;
        //현재 선의 끝 위치
        int end = first_line.y;
        int result = 0;
        //모든 선 긋기 과정 진행
        while(!pq.isEmpty()){
            Info cur = pq.poll();
            //현재 선의 시작 위치가 기존 선의 끝 위치보다 클 때
            //기존 선은 더 이상 연결되지 않는다.
            if(cur.x > end){
                result += end - start;	//기존 선의 길이 구하기
                //새로운 선으로 변경
                start = cur.x;	
                end = cur.y;
                continue;
            }
            //선이 연결되고 기존 선의 끝 위치가 증가할 때
            if(cur.y > end)
                end = cur.y;
        }
        result += end - start;	//마지막 선의 길이 더하기
        bw.write(String.valueOf(result));	//선의 총 길이 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}