[프로그래머스] 빛의 경로 사이클

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 “S”가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 “L”이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 “R”이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

/* 예시 중략 */

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ grid의 길이 ≤ 500
• 1 ≤ grid의 각 문자열의 길이 ≤ 500
• grid의 모든 문자열의 길이는 서로 같습니다.
• grid의 모든 문자열은 ‘L’, ‘R’, ‘S’로 이루어져 있습니다.

---

풀이

75분
빛의 경로를 주어진 조건대로 시뮬레이션 하는 문제였다.
생략되었지만 문제 예시 그림에서는 경로를 표현해주기 위해 격자점 사이에 공간이 있는 것으로 표현되어 있었다. 그래서 문제를 보고 아무런 고민 없이 그림 그대로의 시뮬레이션을 구현하려고 했는데, 격자점의 경계값에서의 동작 처리가 매우 귀찮아진다는 것을 나중에 알게되었다.
그래서 각 격자점에 방향을 포함한 이동 내역을 기록하는 방법으로 풀 수 있었다.

최근에 알고리즘 문제풀이를 소홀히했던 탓인지 문제 난이도에 비해 너무 오랜 시간을 소요했던 것 같다. 그리고 문제를 풀 때는 꼭 펜과 종이를 챙겨야겠다…..

코드

// 03:15 ~ 04: 30
#include <string>
#include <vector>
#include <iostream>

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int n,m;
int board[500][500][4] = {0,};

using namespace std;

int trip(int x, int y, int d, vector<string> grid){
    int dist = 0;
    while(true){
        board[x][y][d] = 1;
        x = (x + dx[d] + n) % n;
        y = (y + dy[d] + m) % m;
        dist += 1;
        
        if(grid[x][y] == 'L') d = (d + 4 - 1) % 4;
        else if(grid[x][y] == 'R') d = (d + 1) % 4;
        
        if(board[x][y][d] == 1) break;
    }
    return dist;
}

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 d = 0; d < 4; ++d){
                if(board[i][j][d] == 0){
                    int dist = trip(i,j,d, grid);
                    answer.push_back(dist);
                }
            }
        }
    }
    sort(answer.begin(),answer.end());
    return answer;
}