프로.2.방문 길이

또또또 이전과 같은 방식으로하다가 털렸다.

 

gemini에게 물어봐서 경로 구하는 법을 알게되었다.

이제 좀 이해하자.

 

경로를 구해야 하는데 좌표를 이용하는 벡터를 사용했다.

그리고 자바 때를 보면 배열로도 못 풀 문제는 아니지만, 더 쉽고 간단한 방법을 배웠다.

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

int solution(string dirs) {  
    int answer = 0;
    int x = 5, y = 5;

    vector<vector<bool>> map(11, vector<bool>(11, 0));

    for (auto dir : dirs)
    {
        if (false == map[y][x])
            ++answer;
        map[y][x] = true;

        switch (dir)
        {
        case 'U': 
            if (y - 1 >= 0) y -= 1;
            break;

        case 'D': 
            if (y + 1 <= 11) y += 1;
            break;

        case 'L':  
            if (x - 1 >= 0) x -= 1;
            break;

        case 'R': 
            if (x + 1 <= 11) x += 1;
            break;
        }
    }

    return answer;
}

 

 

set || map 쌍 좌표를 이용해서 중복을 제거한다. (라고 하지만 중복제거를 활용하진 않음;)

 

 

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

int solution(string dirs) {  
    int answer = 0;
    int x = 0, y = 0;
    //못풀어서 찾아봄
    set<pair<pair<int, int>, pair<int, int>>> path;

    for (auto dir : dirs)
    {
        int nx = x, ny = y;

        if ('U' == dir)  --ny;
        else if ('D' == dir) ++ny;
        else if ('L' == dir) --nx;
        else if ('R' == dir) ++nx;

        if (nx < -5 || nx > 5 || ny < -5 || ny > 5) continue;

        if (path.find({ {x,y} ,{nx,ny} }) == path.end() &&
            path.find({ {nx,ny} ,{x,y} }) == path.end())
        {
            path.insert({ {x,y}, {nx,ny} });
            ++answer;
        }

        x = nx;
        y = ny;
    }

    return answer;
}

 

 

배열 이용한 방법

 

int dy[4] = {0, 0, 1, -1}; // R - L - D - U
int dx[4] = {1, -1, 0, 0};
bool check[11][11][11][11] = {0};

int solution(string dirs)
{
    int answer = 0;

    int y = 5;
    int x = 5;

    memset(check, false, sizeof(check));
    for(int i=0; i<dirs.length(); ++i) {
        int dir;
        if(dirs[i]=='R') dir = 0;
        else if(dirs[i]=='L') dir = 1;
        else if(dirs[i]=='D') dir = 2;
        else if(dirs[i]=='U') dir = 3;

        int ny = y + dy[dir];
        int nx = x + dx[dir];
        if(ny < 0 || nx < 0 || ny > 10 || nx > 10) {
            continue;
        }
        if(!check[y][x][ny][nx]) {
            answer++;
            check[y][x][ny][nx] = check[ny][nx][y][x] = true;
        }
        y = ny;
        x = nx;
    }

    return answer;
}

 

 

책에서는 3차원배열을 이용해서 3번째 인덱스에 방향값 (옵션 1,2,3,4)을 주어 방문을 체크함.