[프로그래머스][C++] 빛의 경로 사이클
빛의 경로 사이클
문제 링크
분석
2차원 배열에서 빛이 특정 규칙에 따라 이동하고, 사이클을 형성하는 경로의 길이를 구하여 반환하는 문제입니다.
매개변수로 주어지는 vector<string> grid는 문자열 배열이며, 요소는 "S", "L", "R"로 구성되어 있습니다.
"S"가 써진 칸은 빛이 직진합니다.
"L"이 써진 칸은 빛이 좌회전을 합니다.
"R"이 써진 칸은 빛이 우회전을 합니다.
격자의 끝을 넘어가면 반대쪽 끝으로 다시 돌아옵니다.
빛은 상, 하, 좌, 우 네 방향 중 하나로 이동합니다.
대각선으로 이동하지 않습니다.
만들 수 있는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 반환해야합니다.
모든 격자 위치와 4가지(상, 하, 좌, 우) 방향에서 빛을 출발시켜서 사이클을 탐색합니다.
각 격자 위치에서의 4가지 방향에 대한 방문 여부를 3차원 배열로 관리하여 저장하면 됩니다.
방문하지 않은 상태의 빛을 이동시키며, 방문을 상태를 변경하고, 이미 방문한 상태에 도달한다면 사이클이 형성된 경우입니다.
사이클이 형성된 경우의 이동 횟수를 기록하여 오름차순으로 정렬하고 반환합니다.
풀이
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<string> grid) {
vector<int> answer;
// 격자의 세로 및 가로 크기 저장
int rows = grid.size();
int cols = grid[0].length();
// 방향을 나타내는 배열로 상, 우, 하, 좌를 가리킨다.
// 상, 우, 하, 좌인 이유는 좌회전 및 우회전 연산을 간편하게 하기 위함입니다.
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
// 각 위치에서 4가지 방향에 대해 방문 여부를 저장하는 3차원 배열
vector<vector<vector<bool>>> visited(rows, vector<vector<bool>>(cols, vector<bool>(4, false)));
// 세로(열) 순회
for (int i = 0; i < rows; ++i)
{
// 가로(행) 순회
for (int j = 0; j < cols; ++j)
{
// 각 방향에서 빛을 출발시키는 반복문
for (int k = 0; k < 4; ++k)
{
// 방문했던 경우 스킵
if (visited[i][j][k])
{
continue;
}
int count = 0;
int curY = i;
int curX = j;
int curDir = k;
// 사이클이 생길때까지 반복한다.
while (!visited[curY][curX][curDir])
{
// 현재 위치의 방향에 대해 방문 처리
visited[curY][curX][curDir] = true;
++count;
// 현재 칸의 문자에 따라 방향 회전
// S인 경우 방향의 변화가 없다.
if (grid[curY][curX] == 'L')
{
// 왼쪽으로 회전
curDir = (curDir + 3) % 4;
}
else if (grid[curY][curX] == 'R')
{
// 오른쪽으로 회전
curDir = (curDir + 1) % 4;
}
// 다음 위치 계산
curY = (curY + dy[curDir] + rows) % rows;
curX = (curX + dx[curDir] + cols) % cols;
}
if (count > 0)
{
answer.push_back(count);
}
}
}
}
sort(answer.begin(), answer.end());
return answer;
}
왼쪽으로 회전(좌회전)을 하는 경우 한 칸 시계 방향으로 돌아가는 것이기 때문에 방향 배열의 값이 1 증가한 것과 같습니다.
오른족으로 회전(우회전)을 하는 경우 한 칸 반시계 방향으로 돌하가는 것이기 때문에 방향 배열의 값이 1 감소한 것과 같습니다.
+ 3 % 4를 하는 것은 -1 +4 % 4를 한 것과 같습니다.
이 방법은 음수를 피하기 위해 사용합니다.
다음 위치를 계산하는 것은 현재 위치에서 방향으로 이동했을 경우의 값을 계산해줍니다.
rows와 cols를 더하는 것은 음수를 방지하기 위함입니다.
성능 요약
시간 복잡도는 $O(rc \ log \ rc)$입니다.
- 격자와 방향에 대한 3중 반복문 $O(r \times c \times 4)$
r은rows를 의미하고,c는cols를 의미합니다.
- 3중 반복문 안에 있는
while$O(r \times c \times 4)$- 방문 처리 기준으로 반복하므로, 모든 격자를 순회할 수 도 있다.
- 정렬 $O(rc \ log \ rc)$
rc는 $r \times c$를 의미합니다.
- $O(r \times c \times 4) \times O(r \times c \times 4) + O(rc \ log \ rc)$
공간 복잡도는 $O(rc)$입니다.
- 각 위치에서 4가지 방향에 대해 방문 여부를 저장하는 3차원 배열
visited$O(r \times c \times 4)$ - 반환할 사이클을 저장한
answer$O(r \times c)$ - $O(r \times c \times 4) + O(r \times c)$
테스트 성능
테스트 1 〉 통과 (0.02ms, 4.14MB)
테스트 2 〉 통과 (0.04ms, 4.17MB)
테스트 3 〉 통과 (0.04ms, 4.19MB)
테스트 4 〉 통과 (1.31ms, 4.2MB)
테스트 5 〉 통과 (2.44ms, 4.75MB)
테스트 6 〉 통과 (2.84ms, 4.48MB)
테스트 7 〉 통과 (40.06ms, 19.1MB)
테스트 8 〉 통과 (36.96ms, 17.2MB)
테스트 9 〉 통과 (77.87ms, 43MB)
테스트 10 〉 통과 (102.40ms, 52.3MB)
테스트 11 〉 통과 (106.91ms, 55.3MB)
댓글남기기