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

문제 설명

S, L , R 방향이 주어진다.

S는 직진, L 은 좌회전, R은 우회전 한다. (빛이 들어온 방향 기준)

기존에 방문한 좌표를 같은 방향으로 재방문한 경우 "싸이클"이 형성된다.

※사이클 : 같은 좌표, 같은 방향 으로 재방문

• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

사이클을 찾고, 각 사이클의 길이를 구하는 문제이다. 

제한 사항

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

입출력 예

grid	result
["SL","LR"]	[16]
["S"]	[1,1,1,1]
["R","R"]	[4,4]

풀이

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

using namespace std;

int N, M;
bool Visit[510][510][4];  //(A, B)에 진행방향 C로 방문한 적이 있습니다.
vector<string> MAP;
          // 0 , 1 ,  2 , 3
          //위, 아래, 오, 왼
int dx[] = { 0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int Chanage_Dir(char C, int Dir){
//   0      : dx, dy  index 번호 기준으로 봤을 때
// 2    3
//   1

    if(C == 'L'){
        if(Dir == 0){ //0의 왼쪽은 3
            return 3;
        }
        if(Dir == 1){ //1의 왼쪽은 2
            return 2;
        }
        if(Dir == 2){ //2의 왼쪽은 0
            return 0;
        }
        if(Dir == 3){ //3의 왼쪽은 1
            return 1;
        }
    }

    if(Dir == 0){ //0의 오른쪽은 2
        return 2;
    }
    if(Dir == 1){ //1의 오른쪽은 3
        return 3;
    }
    if(Dir == 2){ //2의 오른쪽은 1
        return 1;
    }
    if(Dir == 3){  //3의 오른쪽은 0
        return 0;
    }

    return 0;
}

int Simulation(int x, int y, int Dir, int Len){

    if(Visit[x][y][Dir] == true){
        return Len;
    }

    Visit[x][y][Dir] = true;
    int nx = x;
    int ny = y;
    int nd = Dir;

    if(MAP[x][y] != 'S'){
        nd = Chanage_Dir(MAP[x][y], Dir);
    }
    nx = x + dx[nd];
    ny = y + dy[nd];

    //순환할 수 있도록 좌표를 변경해준다.
    if(nx < 0){
        nx = N -1;  //0보다 작으면 max 좌표로 이동
    }
    if(ny < 0){
        ny = M -1;
    }
    if(nx == N){     //max 이면 0 좌표로 이동
        nx = 0;
    }
    if(ny == M){
        ny = 0;
    }

    return Simulation(nx, ny, nd, Len + 1);
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;

    N = grid.size();
    M = grid[0].length();
    MAP = grid;

    for(int i = 0; i < N; i++){           //grid[i][]
        for(int j = 0; j < M; j++){       //grid[i][j]
            for(int k = 0; k < 4; k++){  //방향 검사
                int Result = Simulation(i, j, k, 0);
                if(Result != 0){
                    answer.push_back(Result);
                }
            }
        }
    }

    sort(answer.begin(), answer.end());

    return answer;
}

 

 

다른 풀이

bool is_visit[500][500][4];

vector<int> solution(vector<string> grid) {
    int dir[4][2] = {{0,1}, {-1,0}, {0,-1}, {1,0}};
    vector<int> answer;
    for (int i=0; i<4; i++)
        for (int j=0; j<grid.size(); j++)
            for (int k=0; k<grid[0].size(); k++)
                if (is_visit[j][k][i] == false)
                {
                    int r=j, c=k, d=i, l=1;
                    is_visit[j][k][i] = true;
                    while(1)
                    {
                        if (grid[r][c]== 'L') d = (d+1)%4;
                        else if (grid[r][c] == 'R') d = (4+d-1)%4;
                        r = (grid.size() + r + dir[d][0])%grid.size();
                        c = (grid[0].size() + c + dir[d][1])%grid[0].size(); 
                        if (is_visit[r][c][d]) break;
                        is_visit[r][c][d] = true;
                        l++;
                    }
                    answer.push_back(l);
                }
    sort(answer.begin(), answer.end());
    return answer;
}