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

월간 코드 챌린지 시즌 3

 

그림만 보면 무시무시하지만 실제 풀이는 그렇지 않다.

 

하나의 격자에 빛을 쏘면 내부에서 사이클을 이룬다. 내부에서 퍼지는 게 아니라 하나의 길로 쭉 들어간다고 생각해서 바로 dfs로 풀었다.

 

 

bool cache[501][501][4];

cache 배열이 중요하다

cache[r][c][dir]

r, c 의 격자에 dir 방향으로 들어온 적이 있는지를 체크하는 배열이다.

 

나는 dir 방향으로 들어온 적이 있다면 반드시 그 경우에 해당하는 사이클이 존재한다고 생각했다.

적어도 위 예제만 봐도 모든 경로를 다 탐색한다.

 

만약 다른 예제가 오더라도 아직 방문하지 않은 경로를 시작점으로 탐색을 하는데, 이미 탐색한 다른 경로를 건드릴일이 절대로 없다는 것이다.

    bool &ret = cache[r][c][in];
    // if(ret != false) return;
    ret = true;

위 코드에서 주석 처리된 부분의 주석을 해제하면 이미 탐색한 경로인 경우 넘어간다.

하지만 이 문제에서는 주석 처리된 부분을 그대로 놔둬도 정답이 나온다.

따라서 이미 탐색한 경로를 건드리지 않는다는 가정이 성립한다.

 

 

dfs 인자

void dfs(vector<string> &grid, int sr, int sc, int si, int r, int c, int in, int cnt){

매개변수의 'in'은 현재 좌표로 들어오는 방향을 의미한다.

 

 

dfs 움직임 구현

// 0, 1, 2, 3
// 오, 왼, 아, 위
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

int LEFT[4] = {3, 2, 0, 1};
int RIGHT[4] = {2, 3, 1, 0};

...

    int out;
    
    if(grid[r][c] == 'S'){
        out = in;
    }
    else if(grid[r][c] == 'L'){
        out = LEFT[in];
    }
    else if(grid[r][c] == 'R'){
        out = RIGHT[in];
    }

    int nr = r + dr[out];
    int nc = c + dc[out];

    if(nr < 0) nr = R-1;
    if(nc < 0) nc = C-1;
    if(nr >= R) nr = 0;
    if(nc >= C) nc = 0;
    
    dfs(grid, sr, sc, si, nr, nc, out, cnt+1);
}

out 은 나가는 방향을 의미하는 변수이다.

 

만약 현재 좌표가 'S' 라면 나가는 방향을 in과 똑같이 설정한다.

만약 현재 좌표가 'L 이라면 나가는 방향을 in을 LEFT배열에 넣은 방향으로 설정한다.

dr과 dc배열은 <오른쪽으로, 왼쪽으로, 아래로, 위로> (동서남북 : 0, 1, 2, 3) 으로 나가는 순서로 배열이 저장되어있다.

 

만약 L칸으로 들어온 방향이 '아래로' 였다면 빛이 윗 칸에서 아래의 L칸으로 들어온 것이다.

따라서 빛은 L칸의 오른쪽으로 가야하는데 오른쪽은 dr[0]와 dc[0]를 사용해야한다.

따라서 '아래로' 방향인 2는 0으로 매핑된다.

이런식으로 RIGHT, LEFT 매핑 배열을 만들어주었다.

 

그렇게 in에 맞춰서 out을 설정하고 격자 바깥으로 나갔다면 되돌아오도록 nr, nc를 설정한다.

그리고 다음 격자로 dfs탐색을 계속한다.

 

 

값 도출 조건

if(r == sr && c == sc && si == in && cnt != 0){
        a = cnt;
        return;
    }

최종적으로 현재 좌표가 시작 좌표와 동일하고, 시작할 때 들어왔던 방향과 일치한다면?

현재까지 움직인 거리(cnt)를 답(a)에 저장하고 return한다.

 

 

 

최종 코드

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


using namespace std;

// 0, 1, 2, 3
// 오, 왼, 아, 위

bool cache[501][501][4];
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

int LEFT[4] = {3, 2, 0, 1};
int RIGHT[4] = {2, 3, 1, 0};

int R, C;
// bool check = false;
int a;

void dfs(vector<string> &grid, int sr, int sc, int si, int r, int c, int in, int cnt){
    
    if(r == sr && c == sc && si == in && cnt != 0){
        a = cnt;
        return;
    }
    
    bool &ret = cache[r][c][in];
    // if(ret != false) return;
    ret = true;
    
    int out;
    
    if(grid[r][c] == 'S'){
        out = in;
    }
    else if(grid[r][c] == 'L'){
        out = LEFT[in];
    }
    else if(grid[r][c] == 'R'){
        out = RIGHT[in];
    }

    int nr = r + dr[out];
    int nc = c + dc[out];

    if(nr < 0) nr = R-1;
    if(nc < 0) nc = C-1;
    if(nr >= R) nr = 0;
    if(nc >= C) nc = 0;
    
    dfs(grid, sr, sc, si, nr, nc, out, cnt+1);
}

vector<int> solution(vector<string> grid) {
    memset(cache, 0, sizeof(cache));
    R = grid.size();
    C = grid[0].size();
    vector<int> answer;
    
    int ans;
    for(int i = 0; i < grid.size(); i++){
        for(int j = 0; j < grid[i].size(); j++){
            for(int k = 0; k < 4; k++){
                if(!cache[i][j][k]){
                    dfs(grid, i, j, k, i, j, k, 0);
                    answer.push_back(a);
                    a = 0;
                }
            }
        }
    }
    sort(answer.begin(), answer.end());
    
    return answer;
}