[editorial] 2007년 서울 온사이트 본선 I번 Turtle Graphics

  • 최치선
    최치선

    I - Turtle Graphics
    I번은 실제 대회에 5팀이 푼 문제이지만, 난이도는 높은 편이 아니었습니다.

    배치상 뒤에 있었고, 귀찮다는 점에서 건드리지 않은 팀이 많지 않았나 하는 생각입니다.

    문제를 간단하게 설명하자면 시작점이 (0, 0)이고 lineto명령어 sequence가 들어올 때 교차하는 점이 발생하지 않게 (cycle이 존재하지 않게) cycle을 제거하고 chain 형태로 계속 그렸을 때의 선분의 수와 길이를 구하는 문제입니다.

    모든 명령을 입력받고 그린 다음 최종 그림에 대한 chain을 구하는게 아닌 각 명령이 수행될 때 마다 chain상태를 유지하면서 그리는 것이기 때문에 문제가 쉬워집니다.

    주요 알고리즘은 명령이 하나 들어올 때 마다 이전에 chain에 포함된 선분들을 먼저 그려진 순서대로 교차하는지 검사한 후 교차하는 선분 및 이후에 그려진 선분을 chain에서 제거 해버립니다. 그리고 교차점을 구한 후 교차한 선분의 새로운 시작과 끝을 수정하고 chain에 포함시킵니다.

    주의할 점은 길이가 0인 선분일 경우 포함 시키지 않는 것과 같은 직선상에 두 선분이 놓여질 경우만 조심하면 됩니다.

    상세 구현은 아래에...

    #include <iostream>   
    #include <vector>   
    #include <string>   
    #define X       first   
    #define Y       second   
    #define FROM    first   
    #define TO      second   
    using namespace std;   
    typedef pair<int, int>      Point;   
    typedef pair<Point, Point>  Line;   
    Line drawLine(Point& from, char dir, int len)   
    {   
        Line line(from, from);  
        switch(dir)   
        {   
            case 'E': line.TO.X += len; break;   
            case 'W': line.TO.X -= len; break;   
            case 'N': line.TO.Y += len; break;   
            case 'S': line.TO.Y -= len; break;   
        }   
        return line;   
    }   
    inline int  getLineLength(Line& line)           
    { return abs(line.TO.X - line.FROM.X) + abs(line.TO.Y - line.FROM.Y); }
    inline bool isVertical(Line& l)                 
    { return l.FROM.X == l.TO.X; }
    inline int  ccw(Point& a, Point& b, Point& c)   
    { return (a.X*b.Y + b.X*c.Y + c.X*a.Y - a.Y*b.X - b.Y*c.X - c.Y*a.X); }
    inline bool inLine(Line& l, Point& p)           
    { return (l.FROM.X-p.X)*(l.TO.X-p.X) <= 0 && (l.FROM.Y-p.Y)*(l.TO.Y-p.Y) <= 0; }
    bool intersect(Line& l1, Line& l2)   
    {
        int c1, c2, c3, c4;
        c1 = ccw(l1.FROM, l1.TO, l2.FROM);
        c2 = ccw(l1.FROM, l1.TO, l2.TO);
        c3 = ccw(l2.FROM, l2.TO, l1.FROM);
        c4 = ccw(l2.FROM, l2.TO, l1.TO);
        if(not (c1 | c2 | c3 | c4))
        {
            if( inLine(l1, l2.FROM) || inLine(l1, l2.TO) || 
                inLine(l2, l1.FROM) || inLine(l2, l1.TO))
                return true;
            else return false;
        }
        if(c1*c2 <= 0 && c3*c4 <= 0) return true;
        return false;   
    }
    void process()   
    {   
        string in;   
        cin >> in;   
        int n = in.size() / 2;   
        vector<Line> chain;   
        Point cur(0, 0);   
        for(int i = 0; i < n; i++)   
        {   
            if(in[i*2+1] == '0') continue;   
            // 입력에 해당하는 선분을 그린다.
            Line l = drawLine(cur, in[i*2], in[i*2+1]-'0');    
            // 지금 선분과 교차하는 선분을 찾는다.
            vector<Line>::iterator it;   
            for(it = chain.begin(); it != chain.end() && not intersect(l, *it); it++);   
            // 교차하는 선분이 있을 경우
            if(it != chain.end())   
            {
                Line pl = *it;
                // 교차하는 선분부터 이후에 그려진 선분을 다 지운다.
                chain.erase(it, chain.end());
                // 교차점을 계산한다.
                Point pt;
                pt.X = isVertical(pl) ? pl.FROM.X : l.TO.X;
                pt.Y = isVertical(pl) ? l.TO.Y : pl.FROM.Y;
                // 교차점을 기준으로 선분들을 새로 구성한다.
                l.FROM = pl.TO = pt;
                // 교차한 선분을 chain에 포함시킨다.
                if(getLineLength(pl)) chain.push_back(pl);
                // 지금 그린 선분을 chain에 포함시킨다. 이때 같은 직선상에 있을 경우는 포함시키지 않는다.
                if(isVertical(pl) != isVertical(l))
                    if(getLineLength(l)) chain.push_back(l);
            }   
            else chain.push_back(l);   
            // 마지막 점을 갱신한다.
            cur = l.TO;   
        }   
        int len = 0;   
        for(int i = 0; i < chain.size(); i++)   
            len += getLineLength(chain[i]);   
        cout << chain.size() << " " << len << endl;   
    }   
    int main()   
    {   
        int t;   
        cin >> t;   
        while(t--) process();   
    }  
    

    • imyoyo님 께서 말씀하신 nlogn 방법 훨씬 직관적이고 좋네요 :)

    #include <iostream>   
    #include <vector>   
    #include <string>   
    #include <set>
    #include <map>
    #define X       first   
    #define Y       second   
    using namespace std;   
    typedef pair<int, int>  Point;   
    map<char, Point> move;
    void process()   
    {   
        string in;   
        cin >> in;   
        int n = in.size() / 2;   
        vector<Point>   chain;   
        set<Point>      visited;
        Point cur(0, 0);   
        chain.push_back(cur);
        visited.insert(cur);
        for(int i = 0; i < n; i++)   
        {   
            int m = in[i*2+1] - '0';
            if(m == '0') continue;
            for(int j = 0; j < m; j++)
            {
                cur.X += move[in[i*2]].X;
                cur.Y += move[in[i*2]].Y;
                if(visited.find(cur) != visited.end())
                {
                    for(Point pt = chain.back(); pt != cur; pt = chain.back())
                    {
                        visited.erase(pt);
                        chain.pop_back();
                    }
                }
                else
                {
                    chain.push_back(cur);
                    visited.insert(cur);
                }
            }
        }   
        int cnt = 0;
        for(int i = 1; i < chain.size(); i++)   
        {
            if(i == 1) cnt++;
            else if((chain[i-2].X == chain[i-1].X && chain[i-1].X != chain[i].X) ||
                    (chain[i-2].Y == chain[i-1].Y && chain[i-1].Y != chain[i].Y) )
                cnt++;
        }
        cout << cnt << " " << chain.size()-1 << endl;   
    }   
    int main()   
    {
        move['E'] = Point( 1,  0);
        move['W'] = Point(-1,  0);
        move['N'] = Point( 0,  1);
        move['S'] = Point( 0, -1);
        int t;   
        cin >> t;   
        while(t--) process();   
    }   
    

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
7개의 댓글이 있습니다.
  • 하루
    하루

    H번과 J번에 끼어서 많이들 못 본듯;


    16년 전 link
  • JongMan
    JongMan

    야희~ 코드 어렵따.. ㅠ.ㅠ
    #define 으로 X Y FROM TO 한거 나름 깔끔하다~ ㅋㅋㅋ


    16년 전 link
  • sooshia
    sooshia

    그러게요. pair 쓸때마다 first, second가 지저분하다는 생각을 했었는데
    저런방법이 있었군요


    16년 전 link
  • JongMan
    JongMan

    매크로를 싫어하는 분들은

    pair<int,int> from(const pair<pair<int,int>, pair<int,int> >& p) { return p.first; }
    pair<int,int> to(const pair<pair<int,int>, pair<int,int> >& p) { return p.to; }
    

    같은게 나을 수도 있겠습니다만.. 뭐 이것도 별로 좋진 않군요. ^^;
    저는 요즘은 그냥 struct point같은거 짜는듯한..


    16년 전 link
  • imyoyo
    imyoyo

    저희팀에서는 다른 방법으로 풀었습니다. 간단히 쓰면,
    지나가는 모든 점들을 순서대로 stack으로 쌓아가는데 stack에 이미 존재하는 점이 나오면 그점까지 모두 pop합니다.
    최종 stack의 남은 점들에 대해 꺽이는 회수를 세면 답입니다.
    한 선분당 최대 10개의 점을 가질 수 있기 때문에 점의 개수는 최대 10n개 이고,
    stack에 있는 점들을 set으로 유지하면 stack에 존재하는지 여부를 log시간에 알 수 있습니다.
    따라서 문제 전체가 O(nlogn) 이 됩니다.
    n^2으로 풀기엔 데이터가 커서 많은 팀들이 제껴뒀던것으로 생각됩니다~


    16년 전 link
  • sooshia
    sooshia

    와..훌륭합니다.


    16년 전 link
  • DongJoo
    DongJoo

    I를 연대가 젤 먼저 풀었던걸로 기억하는데..
    그래서 관전자들이 용자팀이라고 했었죠 ㅋㅋ


    16년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.