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

문제 - 빛의 경로 사이클

프로그래머스

■ 문제 설명

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

 

 

풀이과정

이 문제에서 우리가 해야할 것은 다음과 같다.

1. 서로 겹치지 않는 모든 경로 파악하기
2. 그 경로들의 길이 구하기 
3. 오름차순으로 정렬

 

 

1. 서로 겹치지 않는 모든 경로 파악하기

한 격자에서 시작해서 다시 돌아오는 경로를 구하는 것은 쉽다. 문제는 각 격자에서 출발하는 모든 경로들이 서로 같은 경로인지 아닌지를 확인해야한다는 것이다. 

 

핵심 아이디어:

 

모든 격자는 들어오는 방향에 따른 나가는 방향이 정해져 있다.

 

시작점과 상관없이 특정 격자에서 방향이 같으면 전체 경로가 같게 나온다.

 

따라서 우리는 새로운 경로를 다 만들기 전에 시작점에서 방향이 기존의 경로와 겹치는지만 확인하면 된다.

= 모든 경로의 순서를 저장할 필요가 없다.

 

bool map[500][500][4];

우선 방문한 격자와 방향을 저장하기위한 배열을 만들고

 

while(!map[y][x][dir]){
    map[y][x][dir] = true;
    
    [...]
}

조건문에 따라 while문을 돌며 방문한 격자를 저장한다.

조건문은 처음에는 이미 존재하는 경로인지 파악하는 용도로, 그 뒤로는 경로가 끝났는지 확인하는 용도로 사용된다.

 

2. 그 경로들의 길이 구하기

int nodes = 0;
while(!map[y][x][dir]){
    map[y][x][dir] = true;
    nodes++;
    
    [...]
}
if(nodes !=0)
    answer.push_back(nodes);

격자에 방문할 때마다 길이를 카운트한 뒤 길이를 저장한다.

 

3. 오름차순으로 정렬

#include <algorithm>

[...]

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

간단히 algorithm에서 지원하는 정렬을 사용한다.

 

 

전체 코드

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

using namespace std;

bool map[500][500][4];

vector<int> solution(vector<string> grid) {
    vector<int> answer;

    int len_column = grid.size();
    int len_row = grid[0].length();
    int x, y, dir, nodes;

    for (x = 0; x < len_row; x++) {
        for (y = 0; y < len_column; y++) {
            for (dir = 0; dir < 4; dir++) {
                nodes = 0;

                while (!map[y][x][dir]) {
                    //save
                    map[y][x][dir] = true;
                    nodes++;

                    //calculate
                    switch (dir) {
                    case 0: y = (y + len_column - 1) % len_column; break;
                    case 1: x = (x + len_row - 1) % len_row; break;
                    case 2: y = (y + 1) % len_column; break;
                    case 3: x = (x + 1) % len_row; break;
                    }

                    switch (grid[y][x]) {
                    case'S': break;
                    case'L': dir = (dir + 1) % 4; break;
                    case'R': dir = (dir + 3) % 4; break;
                    }
                }

                if(nodes != 0)
                    answer.push_back(nodes);
            }
        }
    }

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

    return answer;
}

---

GitHub - devminjae97/practice: Practice Programming, especially algorithm.