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

[문제 출처]

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

1. 문제

설명

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

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

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

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

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

 

 

제한사항

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

 

입출력 예

 

2. 설명

코드 설명

 1. 모든 격자들을 상하좌우 모두 넣기

h는 세로높이, w는 가로길이, map은 grid의 복사본입니다. 그후 3중포문안에 방향을 i로 dy, dx안에 넣어 4방향을 갈수 있도록 설정하였습니다. dfs안에 현재좌표(y, x), 현재방향(dy[i], dx[i]), 길이를 넣어주었습니다.

 

2. dfs를 통해 길이 구하기

 사이클은 같은 좌표를 지나더라도 방향이 다르면 사이클이 아니므로 visited함수에 좌표와 방향까지 추가해서 같을경우 len을 리턴하도록 구현하였습니다.

 만약 방문한적이 없었다면 1로 고친후, change_dir안으로 넣어 격자를 통과한 방향을 얻어냈습니다. 그후 기존 좌표와 갱신한 방향을 더하고 각 길이의 나머지로 나눠 길이를 넘는상황을 없애주었습니다. 마지막으로 len+1을 하여 dfs를 리턴시켰습니다.

 

3. change_dir을 통해 방향 갱신하기

 S일경우 그대로 리턴, 아닐경우 현재 방향을 old에 저장시킵니다.

if구문을 설정한 예를 하나 들어보면 => oldX==0일경우 아래로 이동할때를 생각해보면 (1,0)이므로 L과 만나면 오른쪽으로 꺾여 (0,1)로 방향이 바뀝니다. 따라서  dirY=oldX; dirX=oldY;로 바꿔줍니다. 나머지 경우도 마찬가지로 실행하였습니다.

 

 

- 오류를 해결하기 위해 고친것

1.     int ny=(y+dirY+h)%h;
        int nx=(x+dirX+w)%w;

        이부분에서 h, w를 더해주지 않았더니 음수로 되는 경우가 있어 segmentation fault가 발생하였습니다.
        그래서 더해주어 음수가 발생하지 않게 고쳐주었습니다.

2.    vector<string> map;

       map=grid;

       dfs함수안에 grid까지 같이 넣어서 반환했더니 시간이 매우 많이 걸려 초과가 되었습니다. 따라서 전체변수로
       map을 설정한뒤 grid를 복사한후 dfs에서 참조해주었더니 시간 조건을 충족할 수 있었습니다.

3. 코드

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

using namespace std;

bool visited[501][501][4][4];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int h,w;
vector<string> map;

void change_dir(char sign, int &dirY, int &dirX){
    if(sign=='S')
        return;
    
    int oldY=dirY;
    int oldX=dirX;
    
    if((oldX==0 && sign=='L') || (oldY==0 && sign=='R')){
        dirY=oldX;
        dirX=oldY;
    }
    else if((oldX==0 && sign=='R') || (oldY==0 && sign=='L')){
        dirY=-oldX;
        dirX=-oldY;
    }
}

int dfs(int y, int x, int dirY, int dirX, int len){
    if(visited[y][x][dirY][dirX]==1)
        return len;
    
    visited[y][x][dirY][dirX]=1;
    change_dir(map[y][x], dirY, dirX);
    int ny=(y+dirY+h)%h;
    int nx=(x+dirX+w)%w;
    
    return dfs(ny,nx,dirY,dirX,len+1);
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    map=grid;
    h=grid.size();
    w=grid[0].size();
    
    for(int y=0; y<h; y++){
        for(int x=0; x<w; x++){
            for(int i=0; i<4; i++){
                int len=dfs(y,x,dy[i],dx[i],0);
                if(len!=0)
                    answer.push_back(len);
            }
        }
    }
    sort(answer.begin(),answer.end());
    return answer;
}