[프로그래머스/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. 문제는 500x500 그리드를 돌면서 사이클을 찾아나간다. (배열이 작아 완전탐색을 고민해 볼 수 있다.)
2. 이때 단순 사이클을 구하는 것이 아니라 방향도 고려해야 하므로 500x500x4 배열로 생각하고 3차원 배열의 사이클로 풀어내야 한다.
3. 오름차순에 주의

이 문제를 풀  때 어떻게 풀어야 하는지는 알겠는데 코드를 작성하는 것이 생각보다 막막했다.

방향 전환을 어떻게 처리할 것이며, 사이클을 어떻게 체크해주어야 하는가 가장 고민이었다.

 

방향은 S를 제외하고는 배열로 만들었을 때 순환적 패턴이 있는 것을 파악해 해결해주었다.

int x_direction[] = {1, 0, -1, 0};
int y_direction[] = (0, 1, 0, -1};

//R방향으로 돈다면 0 -> 1 -> 2 -> 3
//L방향으로 돈라면 3 -> 2 -> 1 -> 0

 

사이클을 체크할 때마다 초기화해야한다고 생각했는데 다시 생각해보니 중복되는 사이클을 제거하기 위해 배열을 계속 들고 가는 형식으로 코드를 작성해야했다.

---

코   드

---

#include <bits/stdc++.h>
using namespace std;
bool visited[501][501][4];
int x_way[] = {1, 0, -1, 0};
int y_way[] = {0, 1, 0, -1};
vector<string> mp;

int change_direction(char c, int way) {
    switch(c) {
        case 'S':
            break;
        case 'R':
            way = (way + 1) % 4;
            break;
        case 'L':
            way--;
            if(way < 0) way = 3;
            break;
    }
    return way ;
}

int simulation(int row, int col, int way, int depth) {
    if (visited[row][col][way]) {
        return depth;
    }
    visited[row][col][way] = 1;
    
    way = change_direction(mp[row][col], way);
    row = row + x_way[way];
    col = col + y_way[way];
    
    if (row < 0) row = mp.size() - 1;
    if (row >= mp.size()) row = 0;
    if (col < 0) col = mp[row].size() - 1;
    if (col >= mp[row].size()) col = 0;
    
    return simulation(row, col, way, depth + 1);
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    mp = grid;
    
    for (int row = 0; row < grid.size(); row++) {
        for (int col = 0; col < grid[row].size(); col++) {
            for (int way = 0; way < 4 ; way++) {
                int cycle_size = simulation(row, col, way, 0);
                if (cycle_size != 0) {
                    answer.push_back(cycle_size);
                }
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}

---

느낀 점: 2단계 맞는지 모르겠다 거의 2주간 풀어냈다.

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

프로그래머스