[프로그래머스/Level 2/C++/월간 코드 챌린지 시즌3] 빛의 경로 사이클

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 각 칸마다 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'로 이루어져 있습니다.

 [문제 풀이]

문제의 핵심은 사이클의 존재를 찾는 것이다.

 

그렇다면 사이클은 어떻게 하면 찾을 수 있을까?

 

먼저, 각 노드별 방향별 방문여부 배열을 만들어 이용하면 쉽게 구할 수 있다.

 

예를 들어 그림의 예제 "S" 노드에서 1번 방향으로 출발한 뒤 돌고 돌아 16번 화살표가 끝나고 난 뒤 다시 반복되는 사이클이 있다.

 

여기서 1번 화살표를 진행할 때 다음 "L" 노드에 대하여 위에서 접근한 적이 있다고 방문여부 배열에 체크를 해준다. 그리고 돌고 돌아서 16번 화살표가 끝나고 난 뒤 다시 "S" 노드에서 아래 "L" 노드에 접근할 때 방문여부가 체크되어있기 때문에 여기서 더 진행을 해도 똑같은 경로로 다시 돌아오기 때문에 더 이상 진행할 필요가 없다. 이때 이동한 횟수를 answer배열에 추가하여 나중에 정렬해서 return 해주면 정답이 된다.

 

참고로 위의 과정을 하나의 노드에서만 진행하면 모든 사이클을 구할 수 없는 경우가 생긴다.

ex) ["S", "S"] 의 경우가 하나의 예다.

 

따라서 모든 노드에 대하여 위 과정을 수행해야 한다.

[소스 코드]

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

using namespace std;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int next_direction(vector<string> &grid, int y, int x, int cur_direction)
{
    char letter = grid[y].at(x);
    if(letter == 'L') return (cur_direction + 1) % 4;
    else if(letter == 'R') return (cur_direction + 3) % 4; 
    else return cur_direction;
}

vector<int> solution(vector<string> grid) {
    int n = grid.size();
    int m = grid[0].size();
    vector<int> answer;
    vector<vector<vector<int>>> dp;
    dp.resize(4);
    for(int i=0; i<4; i++)
    {
        dp[i].resize(n);
        for(int j=0; j<n;j++)
            dp[i][j].resize(m);
    }
    
    for(int y=0; y<n; y++)
    {
        for(int x=0; x<m; x++)
        {
            for(int i=0; i<4; i++)
            {
                int direction = i;
                int cur_y = y; int cur_x = x;

                int cnt = 0;
                while(1)
                {
                    int nx = (cur_x + dx[direction] + m) % m;
                    int ny = (cur_y + dy[direction] + n) % n;

                    if(dp[direction][ny][nx]) break;

                    dp[direction][ny][nx] = true;
                    cnt++;
                    cur_y = ny; cur_x = nx;
                    direction = next_direction(grid, ny, nx, direction);   
                }
                if(cnt == 0) continue;
                answer.push_back(cnt);
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}

굳