BOJ 3442 - 직각 다각형 링크
(2024.04.26 기준 P5)

문제

모든 변이 $X$축 또는 $Y$축에 평행하며 모든 각의 크기가 $90$도 또는 $270$도인 직각 다각형의 모든 꼭짓점이 무작위 순서로 주어질 때, 첫 번째로 주어진 꼭짓점부터 시계방향으로 변이 이어지는 방향 출력

알고리즘

주어지는 직각 다각형의 특징을 파악하고, 정렬을 이용

풀이

축에 평행한 직선마다 포함하는 점의 개수는 무조건 짝수다.
모든 점은 가로 방향의 변 하나와 세로 방향의 변 하나를 잇고 있다. 만약 한 직선에 포함된 점의 개수가 홀수이면, 반드시 점 하나는 직선 방향으로의 변 하나를 잇지 못하게 된다.

또한, 직선에 포함된 점들은 직선 방향으로 정렬했을 때의 앞에서부터 인접한 두 점끼리 변을 이루게 된다.
주어지는 다각형은 두 변이 교차하거나 접하는 경우는 없다. 또한 변을 이루지 않는 점은 없어야 한다. 즉 변의 개수는 점의 개수의 절반이 된다. 그러므로 반드시 인접한 두 점끼리 변을 이루게 된다.

결국 각 직선마다 포함하는 점들을 분류하고 정렬한 뒤, 앞에서부터 인접한 두 점끼리 그래프의 간선을 이루게 한다. 그리고 그래프 탐색을 시작하면 된다.

탐색 시작점은 모든 점을 오름차순으로 정렬했을 때의 가장 첫 번째 점, 즉 가장 왼쪽 아래 점부터 하면 된다. 시계방향으로 방향을 출력한다면 반드시 가장 왼쪽 아래 점은 북쪽으로밖에 갈 수 없다. 즉 방향이 정해진 점부터 시작하면 된다. (반드시 가장 왼쪽 아래 점은 아니어도 된다.)

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1000;

int nxt[MAXN];
char res[MAXN];
vector<int> G[MAXN];
vector<pii> X[20001], Y[20001], P;

void dfs(int i, int p, int s){
    if (s == i) return; // 출발점으로 돌아왔으면 종료
    for (int j: G[i]){
        if (j == p) continue;
        nxt[i] = j;

        // 방향을 찾아야 한다.
        auto [x0, y0] = P[i];
        auto [x1, y1] = P[j];
        if (x0 == x1){
            if (y0 < y1) res[i] = 'N';
            else res[i] = 'S';
        }
        else{
            if (x0 < x1) res[i] = 'E';
            else res[i] = 'W';
        }
        dfs(j, i, s);
        return;
    }
}

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

    int N, sx, sy;
    for (cin >> N; N; cin >> N){

        // 축에 평행한 같은 직선에 포함된 점들을 분류하기 위해
        // 좌표에 10,000씩 더해서 음수를 없앤다.
        cin >> sx >> sy; // 첫 번째로 주어진 점은 따로 저장해놓는다.
        sx += 10000; sy += 10000;
        P.clear(); P.push_back({sx, sy});
        for (int i = 1, x, y; i < N; i++){
            cin >> x >> y;
            P.push_back({x + 10000, y + 10000});
        }

        // 정렬을 해서 탐색을 시작하는 첫 점이 가장 왼쪽 아래 점으로 설정한다.
        // 그래야 무조건 북쪽으로 올라갈 수 있으면서 시계방향이 된다.
        sort(P.begin(), P.end());

        // 점들을 분류한다.
        for (int i = 0; i <= 20000; i++) X[i].clear(), Y[i].clear();
        for (int i = 0; i < N; i++){
            X[P[i].first].push_back({P[i].second, i});
            Y[P[i].second].push_back({P[i].first, i});
        }

        // 각 직선마다 포함된 점들을 정렬한다.
        for (int i = 0; i <= 20000; i++)
            sort(X[i].begin(), X[i].end()), sort(Y[i].begin(), Y[i].end());

        // 각 직선마다 인접한 두 점끼리 잇는다.
        for (int i = 0; i < N; i++) G[i].clear();
        for (int i = 0; i <= 20000; i++){
            for (int j = 0, sz = X[i].size(), u, v; j < sz; j += 2){
                u = X[i][j].second; v = X[i][j + 1].second;
                G[u].push_back(v);
                G[v].push_back(u);
            }
            for (int j = 0, sz = Y[i].size(), u, v; j < sz; j += 2){
                u = Y[i][j].second; v = Y[i][j + 1].second;
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }

        // 시작점의 북쪽에 있는 점을 찾는다.
        auto [x0, y0] = P[0];
        auto [x1, y1] = P[G[0][0]];
        int u;
        if (x0 == x1) u = G[0][0];
        else u = G[0][1];

        nxt[0] = u; // i번째 점 다음에 와야 하는 점
        res[0] = 'N'; // i번째 점으로부터 나아가는 방향
        dfs(u, 0, 0);

        // 첫 번째로 주어진 점의 인덱스를 찾는다.
        int si = 0;
        for (; si < N; si++) if (make_pair(sx, sy) == P[si]) break;

        // 첫 번째로 주어진 점의 인덱스부터 나아가는 방향을 출력한다.
        cout << res[si];
        for (int i = nxt[si]; i != si; i = nxt[i]) cout << res[i];
        cout << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(1111)

def dfs(i, p, s):
    if s == i: # 출발점으로 돌아왔으면 종료
        return
    for j in G[i]:
        if j == p:
            continue
        nxt[i] = j

        # 방향을 찾아야 한다.
        x0, y0 = P[i]
        x1, y1 = P[j]
        if x0 == x1:
            if y0 < y1:
                res[i] = 'N'
            else:
                res[i] = 'S'
        else:
            if x0 < x1:
                res[i] = 'E'
            else:
                res[i] = 'W'
        dfs(j, i, s)
        return

while True:
    N = int(input())
    if not N:
        break

    # 축에 평행한 같은 직선에 포함된 점들을 분류하기 위해
    # 좌표에 10,000씩 더해서 음수를 없앤다.
    sx, sy = map(int, input().split()) # 첫 번째로 주어진 점은 따로 저장해놓는다.
    sx += 10000; sy += 10000
    P = [(sx, sy)]
    for _ in range(N - 1):
        x, y = map(int, input().split())
        P.append((x + 10000, y + 10000))
    input()

    # 정렬을 해서 탐색을 시작하는 첫 점이 가장 왼쪽 아래 점으로 설정한다.
    # 그래야 무조건 북쪽으로 올라갈 수 있으면서 시계방향이 된다.
    P.sort()

    # 점들을 분류한다.
    X = [[] for _ in range(20001)]
    Y = [[] for _ in range(20001)]
    for i, (x, y) in enumerate(P):
        X[x].append((y, i))
        Y[y].append((x, i))

    # 각 직선마다 포함된 점들을 정렬한다.
    for i in range(20001):
        X[i].sort()
        Y[i].sort()

    # 각 직선마다 인접한 두 점끼리 잇는다.
    G = [[] for _ in range(N)]
    for i in range(20001):
        for j in range(0, len(X[i]), 2):
            u = X[i][j][1]; v = X[i][j + 1][1]
            G[u].append(v)
            G[v].append(u)
        for j in range(0, len(Y[i]), 2):
            u = Y[i][j][1]; v = Y[i][j + 1][1]
            G[u].append(v)
            G[v].append(u)

    # 시작점의 북쪽에 있는 점을 찾는다.
    x0, y0 = P[0]
    x1, y1 = P[G[0][0]]
    if x0 == x1:
        u = G[0][0]
    else:
        u = G[0][1]

    nxt = [0] * N; nxt[0] = u # i번째 점 다음에 와야 하는 점
    res = ['N' for _ in range(N)] # i번째 점으로부터 나아가는 방향
    dfs(u, 0, 0)

    # 첫 번째로 주어진 점의 인덱스를 찾는다.
    for si in range(N):
        if (sx, sy) == P[si]:
            break

    # 첫 번째로 주어진 점의 인덱스부터 나아가는 방향을 출력한다.
    print(res[si], end = '')
    i = nxt[si]
    while i != si:
        print(res[i], end = '')
        i = nxt[i]
    print()