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

 

 

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

프로그래머스

 

 

 

목차
1. 문제 접근
2. 풀이
3. 느낀점

 

 

 

 

 

문제 접근

 BFS와 비슷한 개념으로 접근하였다. 큐를 사용하지 않았기에 BFS라고 할순 없지만 방문확인 배열을 사용하여 사이클을 체크하였으므로 BFS와 비슷한 방식이라 볼 수 있다.

 

 

 

 

 

 문제에서 중요한 것은 지금 위치에서 이동하였을 때 사이클이 발생하는 지를 판단할 수 있어야하는 것이었다고 생각한다. 예를 들어 이전에 방문한적이 있는 노드일지라도 그 방향이 다르면 이전과 다른 사이클이 생성될 수 있다는 것이다. 이를 의식하여 방문체크 배열을 3차배열로 만든 후 이 노드에 방문한 시점의 방향까지 체크하게 만들었다. 만약 사이클이 발생하는 경우라면 이전에 방문한 노드이면서 방향까지 같아야 하니 말이다.

 

풀이

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

using namespace std;


// BFS를 활용하여 몇개의 사이클이 가능한지 확인
// 문제점 : 일반적인 방문확인으로는 순환 발생을 체크하기 어려움
// -> 노드와 방문 시의 방향을 같이 기록하는 방식으로 순환을 알 수 있다.

// 3차 배열을 통해 체크
vector<vector<vector<bool>>> check;

int frontX[4]{ 1, 0, -1, 0 }; // 0, 1, 2, 3 순서대로 동남서북
int frontY[4]{ 0, 1, 0, -1 };

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

    check.resize(grid.size());
    for (int i = 0; i < grid.size(); i++) {
        check[i].resize(grid[i].length());
        for (int j = 0; j < grid[i].length(); j++) {
            check[i][j].resize(4); // 방향이 모두 4방향이므로 
            fill(check[i][j].begin(), check[i][j].end(), false);
        }
    }

    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].length(); j++) {
            // 현재 위치에서 시작하여 사이클 길이 체크

            for (int k = 0; k < 4; k++) { // 현재 위치에서 4방향에 대해 사이클 유무 체크
                // k에 의해 4방향을 구분한다.

                int dir = k;
                int cycleCnt = 0; // 이동횟수

                // 현재 위치
                int curX = j;
                int curY = i;

                if (check[curY][curX][dir] == true)
                    continue;

                while (check[curY][curX][dir] == false) { // 이미 방문한 노드가 나올때까지

                    // 현재 지점 방문체크
                    check[curY][curX][dir] = true;

                    int nx, ny = 0;

                    if (grid[curY][curX] == 'S') { // 방향그대로
                        nx = curX + frontX[dir];
                        ny = curY + frontY[dir];
                    }
                    else if (grid[curY][curX] == 'L') { // 좌회전
                        dir--;
                        if (dir < 0)
                            dir = 3;
                        nx = curX + frontX[dir];
                        ny = curY + frontY[dir];
                    }
                    else if (grid[curY][curX] == 'R') { // 우회전
                        dir++;
                        dir = dir % 4;
                        nx = curX + frontX[dir];
                        ny = curY + frontY[dir];
                    }

                    // 다음 도착지점이 맵을 벗어나는지를 체크하여 되돌려놓아야함
                    if (nx < 0)
                        nx = grid[i].length() - 1;
                    else
                        nx = nx % grid[i].length();
                    
                    if (ny < 0)
                        ny = grid.size() - 1;
                    else
                        ny = ny % grid.size();

                    

                    // 현재 지점 갱신
                    curX = nx;
                    curY = ny;


                    // 지금까지의 이동횟수를 기록
                    cycleCnt++;

                }

                if (cycleCnt != 0)
                    answer.push_back(cycleCnt);

            }

        }
    }


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


    return answer;
}

 

 

느낀점

 풀이 자체는 이전에 백준에서 비슷한 문제를 풀었던 경험을 토대로 빨리 떠올렸으나, BFS처럼 큐를 사용해야 할지, 이동은 어떤 식으로 구현해 줘야할 지 고민하여 시간이 많이 걸렸다. 또한 오타가 있었는데 프로그래머스 온라인 컴파일러로는 오타를 못찾아내서 시간안에 풀지도 못했다.

 

 

 비주얼 스튜디오로 디버깅 해보고 나서야 오타를 찾아서 고친 후 정답을 맞췄는데, 다음부터는 좀 침착하게 문제를 풀어야 겠다. 디버깅이 가능했기에 정답을 찾았지 온라인 컴파일러만 쳐다봐선 뭐가 문제인지 발견도 못했을 것 같다. 빨리 익숙해져야겠다.