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

문제 설명

각 칸마다 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

• 문제 예시와 같습니다.
• 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.

입출력 예 #2

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

• 4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.

입출력 예 #3

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

• 2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.

---

문제 풀이

이번 문제는 dfs/bfs 관련 문제라고 생각됩니다.

 

저의 경우 문제에서 원하는 정확한 요구사항을 파악하는데 조금은 무리가 있었지만.. 요약해보자면 각각의 노드에 방향이 정해져있으며, 각각의 경로 사이클 간의 겹침이 없어야 하고 순환이 없도록 경로 사이클의 모든 길이를 구하는 문제입니다.

 

여기서 제가 많이 틀렸던 이유는 문제에서는 각 면의 끝에서만 빛을 발사할 수 있도록 하는 것처럼 보이지만, 사실 모든 노드에서 4가지 방향으로 빛을 발사하는 경우가 존재한다는 것 때문입니다.

 

저는 문제에서 노드별 4방향 방문처리를 위해 3차원 배열을 선언하였습니다.

 

다음으로 중요한 방향 회전은 다음과 같이 4방향 기준 변화량을 저장하는 배열을 선언하였으며,

 

해당 배열을 사용해 'L'(왼쪽)의 경우 무조건 -1 인덱스 위치에 있고, 'R'(오른쪽)의 경우 무조건 +1 위치에 있는 것을 활용해 다음과 같이 노드 방문 시 다음 칸으로 전진 방향을 수정하였습니다.

 

왼쪽의 경우 -1을 하면 인덱스 에러가 발생할 수도 있기에 동일한 위치를 선택하는 +3을 해준 다음 4로 나누어 나머지 값으로 판정하였습니다.

 

위와 같은 방식으로 모든 노드를 순회하며 4가지 방향으로 출발할 경우 순환이 만들어지는 count를 구해 문제를 해결하게 되었으며 문제 자체가 난해하여 이해하는데 시간이 오래 걸리고 힘들었지만, 실제 풀이는 간단한 문제였습니다.

정답 코드

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

using namespace std;

// 위쪽(0), 오른쪽(1), 아래쪽(2), 왼쪽(3)
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};

// 4방향 방문처리용 배열
bool visited[502][502][4];

// grid 캐싱
vector<string> board;

int dfs(int y, int x, int dir, int sizeY, int sizeX, int cnt)
{
    if (visited[y][x][dir]) return cnt;
    
    visited[y][x][dir] = true;
    
    // 방향 조정
    if (board[y][x] == 'L')
        dir = (dir + 3) % 4;
    else if (board[y][x] == 'R')
        dir = (dir + 1) % 4;
    
    // 다음 칸 구하기
    int ny = (y + dy[dir] + sizeY) % sizeY;
    int nx = (x + dx[dir] + sizeX) % sizeX;
    
    return dfs(ny, nx, dir, sizeY, sizeX, cnt + 1);
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    
    // S : 직진
    // L : 좌회전
    // R : 우회전
    // 범위를 벗어나면 반대쪽 끝으로 돌아옴
    
    board = grid;
    
    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid[0].length(); j++)
        {
            for (int k = 0; k < 4; k++)
            {
                int count = dfs(i, j, k, grid.size(), grid[0].length(), 0);
                if (count)
                {
                    answer.push_back(count);
                }
            }
        }
    }
    
    // 오름차순으로 정렬합니다.
    sort(answer.begin(), answer.end());
    
    return answer;
}