프로그래머스 | Level 2 | 빛의 경로 사이클
Programmers | Level 2 | 빛의 경로 사이클
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Breadth-First Search
Description
각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.
- 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
- 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
- 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
- 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.
예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.
이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.
격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.
Constraints
- 1 ≤
grid의 길이 ≤ 500- 1 ≤
grid의 각 문자열의 길이 ≤ 500 grid의 모든 문자열의 길이는 서로 같습니다.grid의 모든 문자열은'L', 'R', 'S'로 이루어져 있습니다.
- 1 ≤
Examples
| grid | result |
|---|---|
["SL","LR"] | [16] |
["S"] | [1, 1, 1, 1] |
["R", "R"] | [4, 4] |
Solutions
Code
import java.util.*;
class Solution {
private static final int[] dx = {-1, 0, 1, 0}; // 상하좌우 이동을 위한 x축 델타 배열
private static final int[] dy = {0, 1, 0, -1}; // 상하좌우 이동을 위한 y축 델타 배열
public int[] solution(String[] grid) {
int rows = grid.length;
int cols = grid[0].length();
// 방문 여부를 추적하는 3차원 배열, 각 칸과 방향마다 확인
boolean[][][] marked = new boolean[rows][cols][4];
List<Integer> cycles = new ArrayList<>();
// 각 칸과 모든 방향으로부터 사이클을 탐색
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
for (int d = 0; d < 4; d++) {
int cycleLength = bfs(new int[]{i, j, d}, marked, rows, cols, grid);
if (cycleLength != 0) cycles.add(cycleLength); // 사이클이 발견된 경우 추가
}
}
}
// 사이클 길이 배열을 오름차순 정렬하여 반환
return cycles.stream().sorted().mapToInt(Integer::intValue).toArray();
}
private int bfs(int[] start, boolean[][][] marked, int rows, int cols, String[] grid) {
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(start);
int distance = 0; // 사이클의 길이를 추적하는 변수
while (!queue.isEmpty()) {
int[] current = queue.poll();
int cx = current[0], cy = current[1], cd = current[2];
// 사이클이 형성되는지 확인
if (marked[cx][cy][cd]) {
// 시작 위치와 다를 때는 유효하지 않은 사이클로 간주
if (start[0] != cx || start[1] != cy || start[2] != cd) distance = 0;
break;
}
// 현재 위치 및 방향을 방문으로 마크하고 거리 증가
marked[cx][cy][cd] = true;
distance++;
// 다음 방향을 결정
int nextDirection = cd;
if (grid[cx].charAt(cy) == 'R') nextDirection = (cd + 1) % 4;
if (grid[cx].charAt(cy) == 'L') nextDirection = (cd + 3) % 4;
// 다음 위치로 이동 (격자 밖으로 나가면 반대쪽으로 돌아옴)
int nx = (dx[nextDirection] + cx + rows) % rows;
int ny = (dy[nextDirection] + cy + cols) % cols;
queue.offer(new int[]{nx, ny, nextDirection});
}
return distance;
}
}
Approaches
이 문제는 격자 내에서 빛의 이동 경로를 추적하여 사이클을 찾아내는 문제로, 그래프 탐색을 통해 사이클을 찾는 전형적인 문제입니다. 각 방향에서 빛을 쏘며, 사이클을 탐색하고 그 길이를 기록합니다.
1. 문제 분석
이 문제는 격자의 각 칸이 빛의 방향을 조정하며, 경계를 넘어가는 특성을 갖는 순환 경로(사이클)를 찾는 문제입니다. 격자의 각 칸은 빛을 직진(S), 좌회전(L), 우회전(R) 시키며, 칸을 빠져나가면 반대편에서 이어지는 토러스 형태의 구조를 갖고 있어, 격자 내에서 사이클이 형성됩니다. 목표는 각 칸에서 출발한 빛의 이동 경로 중에서 순환 경로(사이클)를 탐지하고, 각 사이클의 길이를 계산하여 오름차순으로 반환하는 것입니다.
격자의 구조와 빛의 이동 특성상, 문제는 다음과 같은 분석이 필요합니다:
- 경로 탐색 및 방향 유지: 각 칸에서 빛은 4개의 가능한 방향(상, 하, 좌, 우)으로 이동할 수 있으며, 칸의 특성에 따라 방향이 변경됩니다. 이를 통해 반복되는 경로(사이클)가 형성될 수 있고, 각 경로의 길이를 기록해야 합니다.
- 방문 여부 추적: 각 칸에서의 4가지 방향을 각각 방문 여부로 추적합니다. 같은 칸을 같은 방향으로 다시 방문하면 사이클이 형성된 것으로 간주하고, 그 길이를 계산합니다. 이 과정에서 방문 여부를 효과적으로 관리하여 불필요한 중복 탐색을 방지합니다.
- 경계 순환 처리: 격자 경계를 넘어가면 반대편 끝에서 이어지도록 처리하여, 빛이 격자를 벗어나지 않고 연속적으로 이동할 수 있게 합니다. 이를 통해 격자 내에서 모든 경로를 탐색하여 사이클을 검출합니다.
격자 내 모든 칸의 각 방향에서 시작하는 빛의 이동을 추적하여 사이클이 형성되었는지 확인하고, 사이클이 완성될 때마다 그 길이를 기록하여 최종적으로 사이클의 길이를 오름차순으로 반환합니다.
2. 접근 방식
격자의 모든 칸과 각 방향을 기준으로 사이클을 탐색하기 위해 BFS를 사용합니다. 각 이동에서 격자 특성에 따라 방향이 변경되며, 같은 위치와 방향으로 돌아오는 경우 사이클이 형성됩니다. 이 접근 방식은 다음 단계로 구성됩니다.
- 방향 델타 배열 초기화: 빛이 이동하는 네 가지 방향(상, 우, 하, 좌)에 대해 델타 배열을 설정하여 방향 이동 시 사용할 수 있도록 합니다.
- 모든 위치와 방향에서의 사이클 탐색: 각 칸과 각 방향을 기준으로 BFS를 통해 이동 경로를 탐색합니다. 이미 방문한 위치와 방향은 3차원 배열을 통해 체크하고, 새롭게 사이클을 발견하면 길이를 계산해 리스트에 추가합니다.
- 격자의 특성에 따른 방향 전환: 격자의 각 칸에서 빛이 도달할 때 해당 칸의 정보(S, L, R)에 따라 방향이 변경되며, 격자 끝을 넘어갈 경우 반대편으로 돌아와야 하므로, 모듈로 연산을 통해 위치를 조정합니다.
- 사이클의 길이 기록: BFS로 각 사이클의 길이를 계산한 후, 결과 리스트에 저장하고 최종적으로 정렬하여 반환합니다.
3. 사이클 탐색 초기화
각 칸과 각 방향에서의 이동 경로를 추적하여 사이클을 탐지하기 위해 초기화 작업을 수행합니다. 격자의 모든 칸에서 빛이 이동할 때, 각각의 방향(상, 하, 좌, 우)에 대해 이미 방문한 경우를 기록하기 위해 3차원 배열을 사용하여 방문 여부를 관리합니다. 이렇게 함으로써 중복된 경로 탐색을 방지하고, 새로운 사이클이 시작될 때만 탐색이 이루어지도록 설정합니다. 모든 사이클의 길이를 저장할 리스트도 준비하여, 탐색이 완료된 후 최종적으로 사이클 길이를 정리할 수 있도록 합니다.
int rows = grid.length; // 격자의 행 개수
int cols = grid[0].length(); // 격자의 열 개수
boolean[][][] marked = new boolean[rows][cols][4]; // 각 칸과 방향별로 방문 여부를 저장하는 3차원 배열 [X좌표, Y좌표, 방향]
List<Integer> cycles = new ArrayList<>(); // 모든 사이클의 길이를 저장할 리스트
4. 모든 위치와 방향에서 사이클 탐색
격자의 모든 X좌표와 Y좌표, 그리고 네 방향 각각에서 빛의 경로를 탐색해 사이클을 형성하는지 확인합니다. 이를 위해 각 칸의 각 방향을 시작점으로 설정하고, BFS를 사용해 이동 경로를 추적합니다. 만약 경로가 사이클을 형성하면, 해당 사이클의 길이를 계산하여 결과 리스트에 추가합니다.
for (int i = 0; i < rows; i++) { // 격자의 각 X좌표
for (int j = 0; j < cols; j++) { // 격자의 각 Y좌표
for (int d = 0; d < 4; d++) { // 각 칸의 [상, 하, 좌, 우] 방향
int cycleLength = bfs(new int[]{i, j, d}, marked, rows, cols, grid); // BFS로 사이클 길이 계산
if (cycleLength != 0) cycles.add(cycleLength); // 유효한 사이클의 경우 리스트에 추가
}
}
}
5. BFS를 통한 사이클 길이 탐색
사이클을 찾기 위해 BFS를 사용하여 빛의 이동 경로를 추적합니다. 각 칸의 특성에 따라 빛의 진행 방향을 변경하며, 이미 방문했던 위치와 동일한 방향으로 다시 도달한 경우 사이클이 형성된 것으로 간주하고 사이클의 길이를 반환하여 기록합니다.
특히 격자의 끝을 넘어서는 경우에는 "토로이달 랩어라운드"(toroidal wrap-around) 방식을 적용합니다. 이 방식은 빛이 격자의 끝을 벗어났을 때 반대편 끝으로 이동하게 하여 격자 내에서 계속 순환하도록 만듭니다. 이를 위해 모듈로 연산을 사용하여 경계 밖으로 나간 경우 반대편 끝으로 이동시킵니다.
private int bfs(int[] start, boolean[][][] marked, int rows, int cols, String[] grid) {
Deque<int[]> queue = new ArrayDeque<>();
queue.offer(start); // 시작 위치와 방향을 큐에 추가
int distance = 0; // 사이클 길이 초기화
while (!queue.isEmpty()) {
int[] current = queue.poll();
int cx = current[0], cy = current[1], cd = current[2];
// 이미 방문한 위치와 방향에 도달한 경우, 사이클이 형성된 것으로 간주
if (marked[cx][cy][cd]) {
// 시작 위치와 다르면 유효한 사이클이 아니므로 길이 0으로 설정
if (start[0] != cx || start[1] != cy || start[2] != cd) distance = 0;
break;
}
// 현재 위치와 방향을 방문 표시하고 사이클 길이를 증가
marked[cx][cy][cd] = true;
distance++;
// 다음 이동 방향 설정: 현재 칸의 문자에 따라 방향을 회전
int nextDirection = cd;
if (grid[cx].charAt(cy) == 'R') nextDirection = (cd + 1) % 4; // 우회전
if (grid[cx].charAt(cy) == 'L') nextDirection = (cd + 3) % 4; // 좌회전
// 다음 위치 계산: 모듈로 연산을 통해 격자를 벗어난 경우 반대편 끝으로 이동
int nx = (dx[nextDirection] + cx + rows) % rows;
int ny = (dy[nextDirection] + cy + cols) % cols;
// 다음 위치와 방향을 큐에 추가하여 경로를 계속 추적
queue.offer(new int[]{nx, ny, nextDirection});
}
return distance; // 탐색이 완료되면 사이클의 길이를 반환
}
방향 전환과 토로이달 랩어라운드(Toroidal Wraparound) 계산은 다음과 같은 방식으로 이루어집니다:
- 방향 전환 설정: 각 칸의 특성에 따라 빛이 이동하는 방향이 변경됩니다. 빛이 특정 칸에 도달할 때, 칸의 값이
R이면 빛이 우회전하고,L이면 좌회전합니다. 우회전은 현재 방향에 1을 더하고, 좌회전은 3을 더한 값을 사용해 방향을 갱신합니다. 이때, 방향은 네 가지(상, 우, 하, 좌)로 순환하므로 방향 값이 4를 초과하지 않도록 연산 결과에 모듈로 연산을 적용합니다.S는 직진을 의미하므로, 현재 방향을 그대로 유지합니다. - 토로이달 랩어라운드: 격자의 끝을 넘어가면 반대편 끝에서 이어져야 하므로, 격자의 경계를 초과할 경우 반대쪽 끝으로 이동하도록 모듈로 연산을 적용합니다. 예를 들어, 격자에서 빛이 왼쪽 끝을 넘어가면 오른쪽 끝으로, 위쪽 끝을 넘어가면 아래쪽 끝으로 이동하게 됩니다. 이를 위해 이동하려는 행과 열의 좌표에 격자의 총 행과 열 수를 더한 후, 이를 격자의 크기로 나눠 이동 좌표를 설정합니다. 이 방식으로 격자 바깥으로 나가는 경우에도 빛의 이동이 원활하게 이어지며, 모든 이동이 격자 안에서 순환됩니다.
6. 사이클 길이 오름차순 정렬 및 최종 결과 반환
모든 사이클의 길이가 계산되면, 리스트에 저장된 사이클 길이들을 오름차순으로 정렬한 후 배열로 변환해 반환합니다. 이렇게 정렬된 배열은 문제에서 요구하는 형태로 각 사이클의 길이를 반환하게 됩니다.
// 결과 배열 반환: 오름차순 정렬 후 배열로 변환
return cycles.stream()
.sorted()
.mapToInt(Integer::intValue)
.toArray();
Complexity
- ⏳ TC: O(N^2 × M^2)
- 💾 SC: O(N × M)
격자의 모든 셀과 각 방향에 대해 사이클을 찾기 위해 BFS를 수행합니다. 모든 칸과 방향에서 반복적으로 사이클을 확인하므로 시간 복잡도는 O(N^2 × M^2)입니다. 또한, 방문 여부를 추적하기 위해 사용하는 3차원 배열의 공간 복잡도는 O(N × M)입니다. BFS와 방향 전환을 통해 각 경로에서 효율적으로 사이클을 탐색하여 문제의 요구를 충족합니다.
- Algorithm
- BFS