취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21237번 문제인 Clockwise Fence이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/21237

이 문제에서는 x, y축에 수직이거나 수평한 길이 1인 변으로 이루어진 도형의 꼭짓점이 시계방향순으로 주어지는지 반시계방향순으로 주어지는지 출력하는 문제이다.

주어지는 다각형이 볼록다각형이라면 그냥 다각형을 구성하는 (한 직선 위에 있지 않은) 세 점을 골라 CCW 여부를 확인하면 되겠지만, 이 문제에서는 볼록다각형이라는 조건이 없으므로 CCW 계산만으로는 문제를 해결할 수 없다.

대신, 다각형의 넓이를 계산하는 사선공식(Shoelace Formula)을 이용하여 주어진 꼭짓점이 시계방향 순으로 주어졌는지 반시계방향 순으로 주어졌는지를 알아낼 수 있다.

사선공식의 계산 결과값이 양수일 경우 꼭짓점은 반시계방향 순으로 주어진 것이고, 음수일 경우 꼭짓점은 시계방향순으로 주어진 것이라고 판단할 수 있기 때문이다. 넓이가 0이 나오는 경우는 이 문제에서는 존재하지 않으므로 신경쓰지 않는다.

사선공식에 대하여 잘 모른다면 다음 링크를 참고하자.

en.wikipedia.org/wiki/Shoelace_formula

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int x[101];
int y[101];

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

    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        int ans = 0;
        int xx = 0, yy = 0;
        int slen = (int)s.length();
        for (int i = 0;i < slen;i++) {
            if (s[i] == 'N') yy++;
            else if (s[i] == 'S') yy--;
            else if (s[i] == 'W') xx--;
            else xx++; // else if (s[i] == 'E')
            x[i] = xx;
            y[i] = yy;
        }
        for (int i = 0;i < slen;i++) {
            ans += x[i] * y[i + 1] - x[i + 1] * y[i];
        }
        if (ans > 0) cout << "CCW\n";
        else cout << "CW\n";
    }
}

ps. 위 코드에서, Fence를 설치하기 시작한 좌표는 (0,0)이라고 가정하였다.

시작 좌표가 (0,0)이므로 맨 처음 좌표가 포함된 성분의 값은 0이 된다. 또한, 주어진 대로 펜스를 설치하면 맨 마지막에 다시 시작한 좌표인 (0,0)을 입력하게 되어, 이전에 입력된 값들의 영향을 받지 않고 ans에 0을 더하면서 식 계산을 마칠 수 있다. 따라서 위 코드는 올바른 결과값을 출력한다.