[Algorithm] Programmers :: 방문 길이

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

int changeDir(int dir)
{
    switch (dir)
    {
    case 0: return 1;
    case 1: return 0;
    case 2: return 3;
    case 3: return 2;
    }
}
 
int solution(string dirs) 
{
    int answer = 0;
 
    map<char, vector<int>> dir = { {'U',{-1,0,0}},{'D',{1,0,1}}, {'L',{0,-1,2}}, {'R',{0,1,3}} };
    int arr[12][12][4] = { false };
    int curY = 5;
    int curX = 5;
    int maxY = 10;
    int maxX = 10;
 
    for (int i = 0; i < dirs.size(); ++i)
    {
        int nextY = curY + dir[dirs[i]][0];
        int nextX = curX + dir[dirs[i]][1];
 
        if (nextY < 0 || nextY > maxY) continue;
        if (nextX < 0 || nextX > maxX) continue;
 
        int curDir = dir[dirs[i]][2];
        int changedDir = changeDir(curDir);
 
        if (arr[nextY][nextX][changedDir] == 0)
        {
            ++answer;
            arr[nextY][nextX][changedDir] = 1;
            arr[curY][curX][curDir] = 1;
        }
 
        curY = nextY;
        curX = nextX;
    }
 
    return answer;
}

배열의 인덱스에는 -가 없으니까 시작위치를 0,0대신 5,5로 잡는다.

그리고 이동을 하면서 체크를 할건데 체크를 위한 arr은 [12][12][4]이다..!

3차원인 이유는, 각방향에서 해당칸으로의 접근을 체크하기위해서이다.

헷갈리지 말아야할 것은, 해당칸의 이동이 중복되면 안되는게 아니라, 칸과 칸 사이의 사잇길이 중복되면 안된다는 것이다.

그렇기 때문에 각 방향을 따로 검사해줘야 하고, 0,0에서 1,0을 가는 길과 1,0에서 0,0을 가는길은 하나이기 때문에 따로 카운팅하면 안된다.

그렇기 때문에 방문체크를 할때 각 칸의 사잇길을 향한 방향부분을 true로 체크해줘야 한다.