프로그래머스 빛의 경로 사이클 - C++ 풀이

---

 

1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다.
2. 그리드의 문자열 값에 따라 방향 간선을 추가한다.
3. DFS로 모든 노드를 방문하면서 사이클을 모두 찾아낸다.

 

1. 기존의 노드를 도착한 빛의 방향에 따라 4개의 노드로 쪼갠다.

 노드에 빛이 도달할 때 4가지 경우가 있다. 북쪽에서 도달한 경우, 동쪽에서 도달한 경우, 남쪽에서 도달한경우, 서쪽에서 도달한 경우. 이 4가지 경우는 모두 다른 경우이기 때문에 기존 노드들을 모두 4개로 쪼개서 도달한 빛의 방향에 따라 다른 노드로 보자.

 

2. 그리드의 문자열 값에 따라 방향 간선을 추가한다.

 이제 그리드의 문자열 값에 따라 방향 간선을 추가하여 그래프를 완성한다. L, R인 경우 방향을 전환해주고, 해당 방향으로 1만큼 떨어진 노드로 도착하는 간선을 추가하면 된다.

 

3. DFS로 모든 노드를 방문하면서 사이클을 모두 찾아낸다.

 이제 그래프가 완성되었으므로 DFS를 사용하여 사이클을 찾아주자. 각 노드에서 나가는 간선이 1개 뿐이므로 모든 노드에 대해 한번씩만 방문해주면 모든 사이클을 다 찾을 수 있다.

---

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

using namespace std;

struct Node {
    int r, c, dir;  
};

const int MAX_N = 501;

bool visited[MAX_N][MAX_N][4];
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

Node calcNextNode(Node node, const vector<string>& grid) {
    int N = grid.size();
    int M = grid[0].size();
    
    int nr, nc, ndir;
    
    switch (grid[node.r][node.c]) {
        case 'L':
            ndir = (node.dir + 3) % 4;
            break;
        case 'R':
            ndir = (node.dir + 1) % 4;
            break;
        case 'S':
            ndir = node.dir;
            break;
    }
    
    nr = (node.r + dr[ndir] + N) % N;
    nc = (node.c + dc[ndir] + M) % M;
    
    return {nr, nc, ndir};
}

int DFS(Node node, const vector<string>& grid) {
    if (visited[node.r][node.c][node.dir]) return 0;
    
    visited[node.r][node.c][node.dir] = true;
    return DFS(calcNextNode(node, grid), grid) + 1;
}

vector<int> findAllCycles(const vector<string>& grid) {
    vector<int> ret;
    
    int N = grid.size();
    int 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;
                ret.push_back(DFS({i, j, k}, grid));
            }
        }
    }
    
    sort(ret.begin(), ret.end());
    
    return ret;
}

vector<int> solution(vector<string> grid) {
    vector<int> answer = findAllCycles(grid);
    return answer;
}