문제 푼 날짜 : 2021-11-02

문제

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

접근 및 풀이

문제를 읽던 중, "서로 다른 두 점을 선택하면 하나의 직선이 만들어진다." 라는 부분을 읽고 반사적으로 조합을 떠올렸다.
조합을 구현하여 주어진 좌표들 두 개를 골랐을 때, x 또는 y축과 평행한지 체크해주었다.
하지만, 이는 시간초과라는 처참한 결과로 이어졌고.. 다른 방법을 찾아야했다.

다시 앞서 언급한 문장을 읽었는데 선분이 아니라 직선을 구하는 문제였다.
그래서 C++ STL map을 이용하여 x, y좌표를 각각 key 값으로 하여 갯수를 저장해주었다.
그리고 해당 좌표의 value 값을 2개 이상 갖는 key(x 또는 y좌표)는 x 또는 y 축과 평행한 직선을 형성할 수 있다는 의미이다.

코드(시간초과)

// 백준 2358번 : 평행선
#include <bits/stdc++.h>

using namespace std;

int n, ans = 0;
pair<int, int> p[100001];
bool visited[100001];

void dfs(int idx, int cnt) {
    if (cnt == 2) {
        vector<pair<int, int>> v;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                v.push_back(p[i]);
            }
        }
        int yDiff = abs(v[1].second - v[0].second);
        int xDiff = abs(v[1].first - v[0].first);
        
        if (xDiff == 0 && yDiff > 0) {
            ans++;
        } else if (xDiff > 0 && yDiff == 0) {
            ans++;
        }
        return;
    }
    for (int i = idx; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(i, cnt + 1);
            visited[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
    }
    dfs(0, 0);
    
    cout << ans;
    return 0;
}

코드(통과)

// 백준 2358번 : 평행선
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, ans = 0;
    map<int, int> mx, my;
    cin >> n;

    for (int i = 0, x, y; i < n; i++) {
        cin >> x >> y;
        mx[x]++;
        my[y]++;
    }

    for (auto it = mx.begin(); it != mx.end(); it++) {
        if (it->second >= 2) {
            ans++;
        }
    }
    for (auto it = my.begin(); it != my.end(); it++) {
        if (it->second >= 2) {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

결과

피드백

무지성 코딩은 좋지 않다.. 좀 더 신중히 문제를 풀자.