[코드포스 Practice19] C. Skier

헉

 

이거 전에 그 문제 아녀

 

udlr해서 한바퀴 도는 거!

 

역참조 쓰는게 맞는지 모르겠는데 반가웠다.

 

map 써서 하면 시간복잡도 n * log n이어서 시간복잡도도 만족한다. 

 

암튼 이거 역참조는 생각났는데 코드 구현을 어떻게 할지 몰라서 이전 코드 들고와서 수정했다ㅎㅎ.. 

 

실력 기르기 위해서 내일 다시 짜봐야지 ~.~

 

 

이전 문제는 가장 큰 사이클이 있는지 확인하는 거였는데 이번에는 경로를 저장해야 했다. 

 

처음에는 (0, 0)에서 (0, 1)로 이동하니 이걸 4칸짜리 벡터로 (0, 0, 0, 1) 이렇게 만들까 생각했는데 그럼 (0, 1) (0, 0)은 다른 걸로 인식하고..

 

map<set<pair<int, int>, pair<int, int>>>

 

이런 게 있으면 좋지 않을까 생각했는데 문법이 되는지도 모르겠고 쓸 줄도 몰라서 패스했다.

 

다음으로 생각한 건 점을 저장하고 그 점 주위의 경로를 숫자로 저장하는 거..

 

예를 들어 문자열 N이 들어왔다고 가정해보자.

 

그럼 (0, 0)에서 (0, 1)로 움직였을 것이다.

 

이걸 점 기준으로 생각하면 0, 0은 위쪽으로 길이 있고 0, 1은 아래쪽으로 길이 있을 것이다.

 

그걸 (0, 0) = N, (0, 1) = S 이런 식으로 저장해둔다.

 

하지만 문자열 어떻게 할지 몰라서 (지금은 이게 더 낫지 않을까 생각함ㅋㅋ)

 

숫자 자리수를 SNWE 로 뒀다ㅋㅋㅋ

 

예를 들어 idx[{0, 0}] = 1100 이라면 이건 남쪽, 북쪽으로 경로가 있다는 거

 

ㅋㅋㅋ 악 이게 내 최선이었음

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
using namespace std;
using i64 = long long;
 
int setSNWE(int n, char t)
{
    if (t == 'W')
    {
        if (n%100/10 == 0)
            n += 10;
    }
    else if (t == 'E')
    {
        if (n%10 == 0)
            n += 1;
    }
    else if (t == 'S')
    {
        if (n/1000 == 0)
            n += 1000;
    }
    else if (t == 'N')
    {
        if (n%1000/100 == 0)
            n += 100;
    }
    return n;
}
 
int main() 
{
    int t;
    scanf("%d", &t);
    
    for (int i = 0; i < t; i++)
    {
        string s;
        cin >> s;
        
        map<pair<int, int>, int> idx;
        int x = 0, y = 0;
        int count = 0;
        
        idx[{0, 0}] = 0;
        for (int j = 1; j <= s.size(); j++)
        {
            //cout << s[j-1] << endl;
            int bfr_x = x, bfr_y = y;
            if (s[j-1] == 'W')
                x--;
            else if (s[j-1] == 'E')
                x++;
            else if (s[j-1] == 'S')
                y--;
            else if (s[j-1] == 'N')
                y++;
            
            idx[{bfr_x, bfr_y}] = setSNWE(idx[{bfr_x, bfr_y}], s[j-1]);
            //cout << bfr_x << " " << bfr_y << " " << idx[{bfr_x, bfr_y}] << endl;
            
            //없는 경우
            if (idx.find({x, y}) == idx.end())
            {
                if (s[j-1] == 'W')
                    idx[{x, y}] = setSNWE(idx[{x, y}], 'E');
                else if (s[j-1] == 'E')
                    idx[{x, y}] = setSNWE(idx[{x, y}], 'W');
                else if (s[j-1] == 'S')
                    idx[{x, y}] = setSNWE(idx[{x, y}], 'N');
                else if (s[j-1] == 'N')
                    idx[{x, y}] = setSNWE(idx[{x, y}], 'S');
                count += 5;
                //cout << "없어용" << endl;
            }
            //있는 경우
            else
            {
                bool is_true = false;
            
                if (s[j-1] == 'W')
                {
                    if (idx[{x, y}] == setSNWE(idx[{x, y}], 'E'))
                    {
                        count += 1;
                        is_true = true;
                    }
                }
                else if (s[j-1] == 'E')
                {
                    if (idx[{x, y}] == setSNWE(idx[{x, y}], 'W'))
                    {
                        count += 1;
                        is_true = true;
                    }
                }
                else if (s[j-1] == 'S')
                {
                    if (idx[{x, y}] == setSNWE(idx[{x, y}], 'N'))
                    {
                        count += 1;
                        is_true = true;
                    }
                }
                else if (s[j-1] == 'N')
                {
                    if (idx[{x, y}] == setSNWE(idx[{x, y}], 'S'))
                    {
                        count += 1;
                        is_true = true;
                    }
                }
                if (is_true == false)
                {
                    if (s[j-1] == 'W')
                        idx[{x, y}] = setSNWE(idx[{x, y}], 'E');
                    else if (s[j-1] == 'E')
                        idx[{x, y}] = setSNWE(idx[{x, y}], 'W');
                    else if (s[j-1] == 'S')
                        idx[{x, y}] = setSNWE(idx[{x, y}], 'N');
                    else if (s[j-1] == 'N')
                        idx[{x, y}] = setSNWE(idx[{x, y}], 'S');
                    count += 5;
                }
            }
            //cout << x << " " << y << endl;
            //cout << x << " " << y << " " << idx[{x, y}] << endl;
        }
        
        cout << count << endl;
    }
    
    return 0;
}

 

ㅠㅋ ㅠㅎㅋㅋ 더럽다 정말

 

일단 setSNWE 함수는 현재의 좌표값 (ex 1100)과 방향 'E' 를 넣으면 현재 좌표값에 방향을 업데이트 해준다.

 

코드 중복된 게 많긴 한데 사실 별거 없다.

 

먼저 이동하기 전 좌표값을 방향 업데이트 해준다.

 

다음으로 이동할 좌표가 이미 간 경로인지 확인한다.

 

그다음에 이동한 좌표 업데이트하면 끝~!

 

후 그래도 종료 후 3분 밖에 안 지나서 accept 뜬 거에 만족한다

 

---

ㅋㅋㅋ

ㅋㅋ

처음 이 문제 풀 때 아는 게 나온 줄 알고 과도한 흥분 상태였음 (역참조!!)

 

암튼.. 위에서 이런 식으로 적었었는데

 

이렇게 써도 됐다! (언블리버블)

 

 

와.. 완전 C++ 마스터 같음 코드 개깔끔해

 

코드 분석하면서 들었던 생각인데

 

전에 그래프였나? 트리였나? 그거 피피티 보면서 공부하는데

 

방향 그래프는 하나만 넣어주고 방향 없는 건 경로 두 개 다 넣어줬던 기억이 났다.

 

이것도 그거랑 비슷한듯?

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;

void    calc()
{
    string s;
    cin >> s;
    
    int x = 0, y = 0;
    set<pair<ii, ii>> visited;
    int ans = 0;
    
    for (int i = 0; i < s.size(); i++)
    {
        int nx = x, ny = y;
        
        if (s[i] == 'N')
            ny++;
        if (s[i] == 'S')
            ny--;
        if (s[i] == 'E')
            nx++;
        if (s[i] == 'W')
            nx--;
            
        if (visited.find(pair<ii, ii>(ii(x, y), ii(nx, ny))) != visited.end())
            ans++;
        else
            ans += 5;
        
        visited.insert(pair<ii, ii>(ii(x,y), ii(nx,ny)));
        visited.insert(pair<ii, ii>(ii(nx,ny), ii(x,y)));
        
        x = nx;
        y = ny;
    }
    
    cout << ans << '\n';
}

int     main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++)
        calc();
    
    return 0;
}