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

S, L, R로 채워진 grid가 주어졌을때, 사이클이 있는가 탐색하는 문제이다.

grid의 최대값은 500이므로 char형 배열 board[500][500]을 선언하고,

각 방향에 대해 방문했는지 확인을 위해 int형 배열 moves[500][500]을 선언하였다.

각 위치에서 가능한 방향은 상하좌우 총 4가지이므로 

비트마스크를 통해 방문확인을 한다.

위(0001), 오른쪽(0010), 아래(0100), 왼쪽(1000)

각 방향은 mx,my 배열에 저장되어있다. (↑→↓←)

 

find함수는 이미 진행한 방향을 만나기전까지 경로를 계속 진행하며 탐색하고,(while문)

이미 진행한 방향을 만났을 때의 위치가 시작점이면서,(x==start_x, y==start_y)

처음 방향과 동일하다면(d==start_d)

사이클의 길이를 반환하는 함수이다.

find함수에서 board의 값이 L일때, R일때 방향 d를 바꾸는 작업과

x,y값이 grid의 범위 내인지 확인하는 작업이 중요하다.

L일때는 d=(d+3)%4, R일때는 d=(d+1)%4를 수행하면 된다.

 

moves배열을 전체 탐색하며 진행하지 않은 방향이 있으면 find함수를 호출하여

사이클이 있는지 확인하고 사이클이 있어 -1이 아닌 사이클의 길이가 반환되었다면

해당값을 answer에 push_back 해준다.

 

moves배열 탐색 후 answer을 오름차순으로 sort하면 원하는 결과를 얻을 수 있다.

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

using namespace std;

char board[500][500];
int moves[500][500];
int row, column;
int mx[4] = {-1,0,1,0};
int my[4] = {0,1,0,-1};

int find(int start_x, int start_y, int start_d){
    int x = start_x;
    int y = start_y;
    int d = start_d;
    int count = 0;
    while((moves[x][y] &(1<<d)) != (1<<d)){
        count ++;
        moves[x][y] = (moves[x][y] | (1<<d));
        if(board[x][y]=='L')
            d = (d+3)%4;
        else if(board[x][y]=='R')
            d = (d+1)%4;
        x = x+mx[d];
        y = y+my[d];
        if(x<0)
            x = row-1;
        else if(x>=row)
            x = 0;
        if(y<0)
            y = column-1;
        else if(y>=column)
            y = 0;
    }
    if(x==start_x && y==start_y && d== start_d)
        return count;
    else
        return -1;
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    row = grid.size();
    column = grid[0].size();
    
    for(int i=0; i<row; i++)
        for(int j=0; j<column; j++)
            board[i][j] = grid[i][j];
    int res = 0;
    for(int i=0; i<row; i++){
        for(int j=0; j<column; j++){
            if((moves[i][j] & 1) != 1){
                res = find(i,j,0);
                if(res != -1){
                    answer.push_back(res);
                }
            }
            if((moves[i][j] & 2) != 2){
                res = find(i,j,1);
                if(res != -1){
                    answer.push_back(res);
                }
            }
            if((moves[i][j] & 4) != 4){
                res = find(i,j,2);
                if(res != -1){
                    answer.push_back(res);
                }
            }
            if((moves[i][j] & 8) != 8){
                res = find(i,j,3);
                if(res != -1){
                    answer.push_back(res);
                }
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}