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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/86052

코딩테스트 연습 - 빛의 경로 사이클

1. 주의할 점

- 사이클 여부를 판단해야 한다

- 4방향 탐색을 거친다

 

2. 구현

- Check[y][x][dir] 배열을 통해 각 (y,x)에 dir방향에서 들어온 적이 있는지 확인한다

- Check[][][] 값이 false면 Dfs()를 통해 해당 지점과 방향에서 시작하여 만드는 사이클을 구한다

- Dfs() 내부에서는 이동한 좌표가 범위를 벗어나면 정정해주는 코드를 추가한다

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int row,col;
vector<int> v;
bool check[500][500][4]={false,};
char arr[500][500];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

void dfs(int y, int x, int dir, int len){
    if(check[y][x][dir]){
        v.push_back(len-1);
        return;
    }
    check[y][x][dir]=true;
    char c = arr[y][x];
    int ny,nx,nd=dir;
    if(c=='L')  nd = (dir+3)%4;
    else if(c=='R') nd = (dir+1)%4;
    ny = y+dy[nd];
    nx = x+dx[nd];
    if(ny<0) ny+=row;
    else if(ny>=row) ny-=row;
    if(nx<0) nx+=col;
    else if(nx>=col) nx-=col;
    dfs(ny,nx,nd,len+1);
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    row = grid.size();
    col = grid[0].size();
    
    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            arr[i][j]=grid[i][j];
    
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            for(int k=0;k<4;k++){
                if(check[i][j][k]) continue;
                dfs(i,j,k,1);
            }
        }
    }
    sort(v.begin(),v.end());
    answer = v;
    return answer;
}