[프로그래머스 2레벨] 빛의 경로 사이클 (C++)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
bool visited[501][501][4];
//상, 우, 하, 좌
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int dfs(int x, int y, int dir, vector<string>v)
{
    int cnt = 0;
    while(!visited[x][y][dir])
    {
        cnt++;
        visited[x][y][dir]=1;
        
        if(v[x][y]=='L') dir  = (dir+3)%4; //좌회전
        else if(v[x][y]=='R') dir = (dir+1)%4; //우회전
        
        //격자 끝 넘어가는 경우 방지
        x = (x + dx[dir] + n) % n;
        y = (y + dy[dir] + m) % m;
    }
    return cnt;
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    n = grid.size();
    m = grid[0].size();
    
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            for(int k=0; k<4; k++)
            {
                if(visited[i][j][k]) continue;
                answer.push_back(dfs(i, j, k, grid));
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

 

dfs를 통해 각 방향을 체크한다.

주어진 경로에 대해 방문 여부를 체크하며, 방향이 L인지, R인지에 따라 회전 처리를 해준다.

그리고 회전한 값에 대해 격자 끝이 넘어가는 경우를 방지처리해주어야 한다.

모든 시작점에 대해 사이클을 체크하고, 해당 사이클에 대한 길이를 체크해 반환한다.

미리 선언한 방향 배열과, 좌회전 우회전이 일치하도록 값을 잘 설정해주어야 한다.

 

문제에 주어진 조건에 따라 answer은 무조건 오름차순 정렬을 해서 반환해야한다.