프로그래머스[Lv.2] - 빛의 경로 사이클

문제 설명

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

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

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

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

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

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

 

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

프로그래머스

---

 

 

 

 

 

 

제한 사항

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

---

 

 

 

 

 

 

풀이

모든 노드에서 4방향으로 시작한 뒤 간선의 개수를 세면 된다.

이때, 같은 사이클은 세면 안되기 때문에 방문 여부를 체크한다.

만약 같은 노드에서 같은 방향으로 진행을 했다면 같은 사이클에 포함되는 경우이므로 넘어가도 된다.

 

접근법은 간단하지만 구현하는데 까다로운 부분이 있다.

이차원 벡터의 4방향을 확인해야 하기 때문에 삼차원 벡터의 개념을 사용해야 한다.

하지만, 헷갈릴 수 있기 때문에 이차원 벡터의 메모리 구조를 본떠 일렬로 펴서 일차원 벡터로 변환한다. 

이때, 각 index는 다음과 같이 계산할 수 있다

int idx = (i * grid[0].size() + j);

이렇게 변환한 벡터와 4가지 방향을 나타내는 정보를 담은 이차원 벡터를 이용하여 문제를 풀면 된다.

 

그리고, grid를 넘어가는 순회는 반대쪽 끝에서 돌아오기 때문에 mod연산을 이용하여 구현하면 된다.

// grid size = 4
// j가 3일때(가장 오른쪽에 있을 때) 오른쪽으로 이동

int j = 3;
j = (j+1) % 4;

계산 결과 j = 0이 된다.

이러한 개념은 벡터나 배열을 통해 circular buffer를 구현할 때 사용된다.

이때, 왼쪽 끝에서 왼쪽으로 이동할 경우가 생긴다.

그렇게 되면 index가 음수가 될 수 있다.

위의 식을 다음과 같이 바꾸면 이 문제도 해결 가능하다.

// grid size = 4
// grid[0] size = 3
// j가 30일때(가장 왼쪽에 있을 때) 왼쪽으로 이동

int j = 0;
j = (j - 1 + grid[0].size()) % 4;

행의 요소의 개수를 더한 뒤 mod연산을 적용하면 음수인 부분도 해결이 가능하다.

 

이러한 그래프나 배열을 순회하는 문제를 풀 때 한 가지 팁은 이동하는 방향에 대한 index 증가치를 벡터로 만들어 놓고 받아와 사용하면 편하다.

또한, enum을 이용하여 원하는 방향의 index 증가치를 받아올 수 있다.

하지만, 이 부분은 이번 문제에서 사용할 필요는 없다.

// idx 
// 0: DOWN, 1: LEFT, 2: UP, 3:RIGHT

enum DIR
{
	DOWN,
    LEFT,
    UP,
    RIGHT
};

vector<vector<int>> Dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

---

 

 

 

 

 

전체 코드

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

using namespace std;

int Cycle(int startI, int startJ, int startDir, vector<vector<int>>& Dir, vector<string>& grid, vector<vector<bool>>& visited)
{
    int cnt = 1;
    int currentI = startI;
    int currentJ = startJ;
    int currentDir = startDir;
    
    visited[startI * grid[0].size() + startJ][startDir] = true;
    
    while(true)
    {
        currentI = (currentI + Dir[currentDir][0] + grid.size()) % grid.size();
        currentJ = (currentJ + Dir[currentDir][1] + grid[0].size()) % grid[0].size();
        
        if(grid[currentI][currentJ] == 'L')
        {
            currentDir = (currentDir - 1 + 4) % 4;
        }
        else if(grid[currentI][currentJ] == 'R')
        {
            currentDir = (currentDir+1) % 4;
        }
        
        if(visited[currentI * grid[0].size() + currentJ][currentDir]) break;
        
        visited[currentI * grid[0].size() + currentJ][currentDir] = true;
        cnt++;
    }
    
    return cnt;
}


vector<int> solution(vector<string> grid) {
    vector<int> answer;
    
    vector<vector<bool>> visited(grid.size() * grid[0].size(), vector<bool>(4, false));

    // 4방향
    vector<vector<int>> Dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
    
    for(int i = 0; i < grid.size(); i++)
    {
        for(int j = 0; j < grid[0].size(); j++)
        {
            for(int k = 0 ; k < 4; k++)
            {
                if(visited[i * grid[0].size() + j][k] == true) continue;
                int temp = Cycle(i, j, k, Dir, grid, visited);
                answer.push_back(temp);
            }
        }
    }

    
    sort(answer.begin(), answer.end());
    
    return answer;
}

---