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

https://programmers.co.kr/learn/courses/30/lessons/86052

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

 

풀이

- 한번이라도 지난 간선이라면 다음에 또 그 간선을 지나게되는 경우 이전 사이클과 동일한 사이클을 형성할것이기 때문에 해당 케이스의 경우 바로 제외한다.

- 이 문제에서 생길 수 있는 최대 간선의 개수는 500*500*4 = 10000000 개이다. 1억 이하이기 때문에 완전탐색으로 풀 수 있다.( 한 정점에 도달하는 모든 방향에 대한 간선을 체크해야 하기 때문에 3차원배열을 이용해 체크한다. (오른쪽, 아래, 왼쪽, 위 이렇게 4방향 ))

- 마지막에 정렬을 해줘야 한다. (테스트 케이스를 다 통과하는데 코드 제출을 하면 11번만 통과한다? -> 정렬ㄱㄱ) 

 

소스코드 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int visited[501][501][4];// 오른 , 아래, 왼 , 위
int dx[]= {0,1,0,-1};
int dy[] = {1,0,-1,0};
vector<string> _grid;
vector<int> answer;
int xlen,ylen;
int dfs(int x, int y, int dir, int cnt){
    if(x>=xlen ) x = 0;
    if(y>=ylen ) y = 0;
    if(x<0) x=xlen-1;
    if(y<0) y=ylen-1;
   
    if(visited[x][y][dir]==1){
        return cnt;
    }
    visited[x][y][dir]=1;
    int ndir;
    if(_grid[x][y]=='S') {
        ndir = dir;
    }else if(_grid[x][y]=='L') {
        ndir = (dir+3)%4;
    }else if(_grid[x][y]=='R'){
        ndir = (dir+1)%4;
    }
    
    return dfs( x+dx[ndir],y+dy[ndir], ndir, cnt+1);
}

vector<int> solution(vector<string> grid) {
    
    xlen= grid.size();
    ylen = grid[0].size();
    _grid=grid;
    for (int i=0; i<xlen; i++){
        for (int j=0; j<ylen; j++){
            for (int k=0; k<4; k++) {
                int len = dfs(i,j,k,0);
                if(len>0) answer.push_back(len);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}