C++:: 프로그래머스 < 빛의 경로 사이클 >

주어진 string 구조에 따라서 방향을 따라 만들어 지는 경로의 길이들을 반환하는 문제이다. 문제에 대한 해법을 생각하기 어려운 문제이다. 해당 풀이는 dfs를 통해서 경로를 하나씩 구해 냈다. 난이도에 비해 많이 어려운 문제이다.

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

int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// N, E, S, W
vector<int> answer;

void dfs (int cur_x, int cur_y, int dir, int cnt, vector<vector<vector<bool>>>& vis, vector<string>& grid) {
    if (vis[cur_x][cur_y][dir]) {// 이전에 지나간 경로라면
        answer.push_back(cnt);// 경로 길이 추가
        return ;
    }
    vis[cur_x][cur_y][dir] = true;// 경로 지났음 표시
    int nx = cur_x + dx[dir], ny = cur_y + dy[dir];// 경로를 통해 온 다음 위치
    
    if (nx == -1) nx = n - 1;
    if (nx == n) nx = 0;
    if (ny == -1) ny = m - 1;
    if (ny == m) ny = 0;
    
    if (grid[nx][ny] == 'L') {// 이전 방향에 따른 다음 방향 구하기
        dir = dir - 1 < 0 ? 3 : dir - 1;
    } else if (grid[nx][ny] == 'R') {
        dir = dir + 1 < 4 ? dir + 1 : 0;
    }
    
    dfs(nx, ny, dir, cnt+1, vis, grid);// 다음 위치로 재귀
}

vector<int> solution(vector<string> grid) {
    n = grid.size(); m = grid[0].size();
    /*
    	3차원 배열로 구현하였는데 vis [ x 좌표 ] [ y 좌표 ] [ 동서남북 ] 으로 생각하면 된다.
        핵심은 해당 x, y 좌표에서 동서남북 방향으로의 경로를 이전에 지난적 있는지 체크해주는 부분이다.
    */
    vector<vector<vector<bool>>> vis(n, vector<vector<bool>>(m, vector<bool>(4, false)));
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            for (int dir=0; dir<4; dir++) {
                if (!vis[i][j][dir]) {
                    dfs(i, j, dir, 0, vis, grid);
                }
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}