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

 

 

 

 

 

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

프로그래머스

 

이번 문제는 BFS와 유사한 문제였습니다.

빛이 4방향(상, 우, 하, 좌)으로 이동할 수 있기 때문에 3차원 배열을 사용하여 방문 여부를 확인해 주었습니다.

 

 

 

 

 

📝 문제 풀이

1. 각 칸마다 4개의 방향(상, 우, 하, 좌)으로 getLengthOfCycle 함수 실행

2. 아직 해당 방향으로 빛을 쏘지 않은 칸이라면

    • cnt 변수(경로 사이클의 길이) 1 증가

    • 해당 방향으로 빛을 쏜 칸임을 표시 (visited 배열)

    • 'L'이 써진 칸이라면 (방향 + 3) % 4 값으로 방향 설정 ⭐️⭐️

    • 'R'이 써진 칸이라면 (방향 + 1) % 4 값으로 방향 설정 ⭐️⭐️

    • 다음 좌표를 격자 범위 내의 좌표로 갱신 

3. cnt 변수 반환하여 answer 벡터에 삽입

4. answer 벡터 오름차순 정렬 ⭐️

 

 

 

 

 

👩🏻‍💻 C++ 코드

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

#define MAX 500

using namespace std;

int r, c;
bool visited[MAX][MAX][4];

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

int getLengthOfCycle(int x, int y, int dir, vector<string> grid) {
    int cnt = 0; // 경로 사이클의 길이
    
    while (visited[x][y][dir] == false) {
        cnt += 1;
        visited[x][y][dir] = true;
        
        if (grid[x][y] == 'L') {
            dir = (dir + 3) % 4;
        } else if (grid[x][y] == 'R') {
            dir = (dir + 1) % 4;
        }
        
        // 격자 범위 내의 값으로 갱신
        x = (x + dx[dir] + r) % r;
        y = (y + dy[dir] + c) % c;
    }
    
    return cnt;
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    r = grid.size();
    c = grid[0].size();
    
    for (int i=0; i<r; i++) {
        for (int j=0; j<c; j++) {
            for (int k=0; k<4; k++) {
                if (!visited[i][j][k]) {
                    answer.push_back(getLengthOfCycle(i, j, k, grid));
                }
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    return answer;
}

 

 

프로그래머스 - 결과 화면