[프로그래머스 c++] 빛의 경로 사이클

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

📂 분류

완전 탐색 그래프 탐색 시뮬레이션

💡 풀이

문제를 처음 읽었을 때 이해가 안돼서 문제 예시를 손으로 직접해보니깐 이해가 됐다.

방문처리를 방향이 존재하기 때문에 방향까지 넣어줄 3차원배열을 쓰는게 가장 핵심이다.
모든 방향에 대해 BFS를 써서 탐색하면 된다.
방향 전환 아래와 같이 구현

• L일 때 방향 전환
  • (dir + 1) % 4
• R일 때 방향 전환
  • dir == 0 ? 3 : dir - 1

사이클 처리는 getNumberOfLightCycle() 함수를 호출했을 때 초기 y, x, dir 값을 또 방문했을 경우로 처리했다.
여기서 의문점은

while (!visited[y][x][dir]) {
  ...
}

while (true) {
  if (visited[y][x][dir]) break;
  ...

두 코드 차이점이 없어보이는데 첫 번째 코드로 제출을 하면 마지막 테스트 시간 초과로 실패했다.
이 글을 작성할 때 다시 제출하니 통과하네..?🤔 아마도 채점 서버의 문제였던 것 같다

그리고 answer 값을 반환할 때 꼭 정렬을 해주어야 한다!!
정렬을 해주어야하는지 모르고 뭐가 문제인지 계속 살펴보다가 문제를 다시 읽어보니 정렬을 하여 반환하라고 적혀있었다..

💻 코드

#include <bits/stdc++.h>

using namespace std;

#define MAX 500

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

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

int getNumberOfLightCycle(vector<string> grid, int y, int x, int dir) {
    int cnt = 0;
    
    while (!visited[y][x][dir]) {
        cnt += 1;
        visited[y][x][dir] = true;
        
        if (grid[y][x] == 'L')
            dir = (dir + 1) % 4;
        else if (grid[y][x] == 'R')
            dir = dir == 0 ? 3 : dir - 1;
            
        y = (y + dy[dir] + r) % r;
        x = (x + dx[dir] + c) % c;
    }
    return cnt;
}

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