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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음 이 문제를 봤을 때, 시작점이 정해져 있는지 아니면 정말 말 그대로 특정 격자에서 출발할 수 있는 모든 사이클을 구해야하는지 의문이 들었다.

 

제한사항을 보니 시작점 등의 제한사항이 없기 때문에 말 그대로 모든 사이클을 구하면 되겠다고 생각하고 문제를 풀었다.

 

이 문제에서 핵심은 사이클이다.

 

만약 한 격자에서 왼쪽으로 이동하는 경로가 있다면, 이 경로가 포함된 사이클은 몇 개일까?

정답은 무조건 한 개다.

 

왜냐하면 격자에서 특정한 방향으로 이동하게 되면, 결국에는 돌고 돌아 같은 사이클을 나타내기 때문이다.

 

그래서 사이클을 표시하기 위해 2차원 배열에 4가지 방향으로 이동했음을 저장하는 visited 배열을 만들었다.

그리고 사이클을 따라 이동하면서 방문한 격자의 방향을 true로 변경했다.

 

만약 이동했는데, 격자가 이미 방문한 격자라면 사이클이 끝난 것이다.

 

이렇게 모든 격자에서 특정 방향으로 방문한 기록이 없으면 사이클을 탐색하면 된다.

 

+ R방향과 L방향의 이동을 편하게 나타내기 위해, 상하좌우 순서로 dir을 만들었다.

만약 L격자를 만나면 (dir+1)%4로 왼쪽으로 방향을 바꿔주고, R격자를 만나면 (dir+3)%4로 오른쪽으로 방향을 변경했다.

(S인 경우는 그대로)

 

마지막으로 오름차순으로 sort를 하면 문제가 해결된다.

 

​

[아이디어 정리]

1. 특정 격자에서 특정 방향으로 이동하는 사이클은 무조건 한 개만 존재한다. 
2. 그러므로 사이클을 탐색하다가 이미 방문한 격자를 만나면 그 사이클은 종료가 된다.
3. n*m*4(방향) 을 저장할 vector를 만들어 방문했는지 체크한다.
4. 특정 격자에서 특정 방향으로 방문한 적이 없다면, 사이클이 있으므로 탐색을 시작한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4]={-1,0,1,0};
int dx[4]={0,-1,0,1};
// 상 좌 하 우

int findRoot(vector<vector<vector<bool>>>&visited,vector<string> &grid, int y, int x, int dir)
{
    int answer=0;
    int maxY=grid.size(), maxX=grid[0].length();
    while(!visited[y][x][dir])
    {
        visited[y][x][dir]=true;
        y+=dy[dir]+maxY,x+=dx[dir]+maxX;
        y%=maxY,x%=maxX;
        if (grid[y][x]=='L')
        {
            dir+=1;
            dir%=4;
        }
        else if (grid[y][x]=='R')
        {
            dir+=3;
            dir%=4;
        }
        answer+=1;
    }
    return answer;
}

vector<int> solution(vector<string> grid) {
    vector<int> ans;
    vector<vector<vector<bool>>> visited(grid.size(),vector<vector<bool>>(grid[0].length(),vector<bool>(4,false)));
    for (int i=0; i<grid.size(); i++)
    {
        for (int j=0; j<grid[0].size(); j++)
        {
            for (int k=0; k<4; k++)
            {
                if (!visited[i][j][k])
                {
                    ans.push_back(findRoot(visited,grid,i,j,k));
                }
            }
        }
    }
    sort(ans.begin(),ans.end());
    return ans;
}

 

---

처음에 아무리 생각해도 풀이가 맞는데 전부 틀렸다고 나와서 당황했다.

테스트 케이스를 여러개 추가하고 곰곰히 생각해 봤더니 격자를 이동하는 부분에서 문제가 생길 수 있었다.

y가 0일때, -1 방향으로 이동하고 퍼센트 연산을 하는 과정에서 -1%4가 돼 문제가 생기는 것이었다...

이 부분을 해결했더니 바로 문제가 해결됐다

 

프로그래머스