[Algorithm] Programmers :: 빛의 경로 사이클

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

프로그래머스

struct Node
{
    int y;
    int x;
    int dir;
    int count;
};
 
map<char, vector<int> > dirs =
{
    {'L',{3,0,1,2}},
    {'R',{1,2,3,0}},
    {'S',{0,1,2,3}}
};
 
bool visited[501][501][4] = { false }; // 뻗어나가는 방향 체크.
int dir[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} };
int maxRow = 0;
int maxCol = 0;
 
vector<int> solution(vector<string> grid)
{
    vector<int> answer;
 
    maxRow = grid.size();
    maxCol = grid[0].size();
 
    for (int i = 0; i < maxRow; ++i)
    {
        for (int j = 0; j < maxCol; ++j)
        {
            for (int k = 0; k < 4; ++k)
            {
                if (visited[i][j][k]) continue;
 
                Node curNode = { i,j,k,0 };
                visited[curNode.y][curNode.x][curNode.dir] = true;
 
                while (1)
                {
                    int nextY = curNode.y + dir[curNode.dir][0];
                    if (nextY < 0) nextY = maxRow - 1;
                    else if (nextY >= maxRow) nextY = 0;
 
                    int nextX = curNode.x + dir[curNode.dir][1];
                    if (nextX < 0) nextX = maxCol - 1;
                    else if (nextX >= maxCol) nextX = 0;
 
                    int nextDir = dirs[grid[nextY][nextX]][curNode.dir]; // 다음방향만 지정해주는거
                    int nextCount = curNode.count + 1;
 
                    if (visited[nextY][nextX][nextDir]) // 사이클완성.
                    {
                        answer.push_back(nextCount);
                        break;
                    }
                    else
                    {
                        visited[nextY][nextX][nextDir] = true;
                        curNode = { nextY,nextX,nextDir,nextCount };
                    }
                }
            }
        }
    }
 
    sort(answer.begin(), answer.end());
 
    return answer;
}

문제설명이 애매해서 다른 사람의 설명을 보고나서야 완벽히 이해할 수 있었다.

각 칸마다 4방향에 대해 방문탐색을 하는게 포인트다.

임의의 위치에서 임의의 방향에 대해 이전에 방문한적 없다면 그곳이 출발노드이다.

이후 조건에 따라 이동을하면서 방향에 대해 전부 방문체크를 해주고, '같은 노드의 같은 방향'을 만날 경우 사이클이 형성됐으니 종료시켜주면 된다.