[백준 2170번] 선 긋기 (C++, Python3)

https://www.acmicpc.net/problem/2170

2170번: 선 긋기

이번 포스트에서는 백준 알고리즘 문제인 선 긋기를 포스트하도록 하겠습니다.

 

해당 문제는 solved.ac 기준 골드 5에 위치한 문제입니다.

 

먼저 문제입니다.

선을 그은 횟수 N과 선을 그을때 선택한 두 점의 위치를 입력받습니다.

 

이때, 그려진 선들의 총 길이를 구하여 출력하는 문제입니다.

 

해당 문제는 선이 있는 위치에 겹쳐서도 그릴 수 있기 때문에, 선이 겹쳐서 있는지를 판단하고 겹쳐있다면 더 긴 선으로 교체하면서 길이를 갱신하는 스위핑 알고리즘으로 해결합니다.

 

먼저 C++ 코드 입니다.

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, res = 0;
    cin >> n;
 
    pair<int, int> lines[n];
 
    for(int i = 0; i < n; i++)
        cin >> lines[i].first >> lines[i].second;
 
    sort(lines, lines + n);
 
    int start = lines[0].first;
    int end = lines[0].second;
 
    for(int i = 1; i < n; i++) {
        if(lines[i].start > end) {
            res += end - start;
            start = lines[i].first;
            end = lines[i].second;
        } else {
            end = max(end, lines[i].second);
        }
    }
 
    res += end - start;
    cout << res;
 
    return 0;
}

다음은 Python 코드입니다.

 

import sys
input = sys.stdin.readline
 
n = int(input())
 
lines = [] * n
 
for i in range(n) :
    x, y = map(int, input().split())
    pair = (x, y)
    lines.append(pair)
 
lines.sort(key = lambda k : k[0])
 
start = lines[0][0]
end = lines[0][1]
res = 0
 
for i in range(n) :
    if lines[i][0] > end :
        res += end - start
        start = lines[i][0]
        end = lines[i][1]
    else :
        end = max(lines[i][1], end)
 
res += end - start
print(res)

각 선들의 시작위치와 끝 위치를 저장하고, 시작위치를 기준으로 정렬합니다.

그리고 순서대로 방문하면 다음 선이 현재 저장한 선의 끝위치 보다 뒤에 있을 경우, 현재 까지 저장한 선의 길이를 res에 누적합니다.

 

그게 아니고 겹쳐있다면 선의 끝 위치를 더 긴 선으로 갱신하면서 길이를 증가합니다.

이를 통해 그려진 선의 길이를 누적하고 출력하면 되는문제로 스위핑 알고리즘에 대한 이해만 있다면 어렵지 않은 문제였습니다.

 

다음 포스트에서도 다른 백준 알고리즘 문제로 포스트하도록 하겠습니다. 감사합니다.