빛의 경로 사이클

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/f3c02c50-f82e-45d0-b633-ad3ecadba316/ex1.png

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ grid의 길이 ≤ 500
  • 1 ≤ grid의 각 문자열의 길이 ≤ 500
  • grid의 모든 문자열의 길이는 서로 같습니다.
  • grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

---

입출력 예

grid result

["SL","LR"]	[16]
["S"]	[1,1,1,1]
["R","R"]	[4,4]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.
• 길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.

입출력 예 #2

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/88a2717d-14ab-4297-af06-00baab718080/ex2.png

• 4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.

입출력 예 #3

• 주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.

!https://grepp-programmers.s3.ap-northeast-2.amazonaws.com/files/production/076dbe07-2b33-414e-b6db-1e73ae2055f3/ex3.png

• 2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.

package LV2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class H86052 {
	int[] dr = {-1, 0, 1, 0}; // up, right, down, left
	int[] dc = {0, 1, 0, -1}; // up, right, down, left
	int[][][] visited; // grid 상태를 기록하는 배열
	int[][][] moveCount; // 각 점에서의 이동 수를 저장하는 배열
	String[] grid;
	int n, m;

	public int[] solution(String[] grid) {
		this.grid = grid;
		n = grid.length;
		m = grid[0].length();
		visited = new int[n][m][4];
		moveCount = new int[n][m][4];
		List<Integer> cycles = new ArrayList<>();

		int count = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				for (int k = 0; k < 4; k++)
					if (visited[i][j][k] == 0)
						DFS(i, j, k, ++count, 1, cycles);

		Collections.sort(cycles);
		return cycles.stream().mapToInt(i -> i).toArray();
	}

	private void DFS(int row, int col, int dir, int count, int moves, List<Integer> cycles) {
		if (visited[row][col][dir] != 0) {
			if (visited[row][col][dir] == count)
				cycles.add(moves - moveCount[row][col][dir]);
			return;
		}

		visited[row][col][dir] = count;
		moveCount[row][col][dir] = moves;

		if (grid[row].charAt(col) == 'L') dir = (dir + 3) % 4;
		else if (grid[row].charAt(col) == 'R') dir = (dir + 1) % 4;

		int nrow = (row + dr[dir] + n) % n;
		int ncol = (col + dc[dir] + m) % m;

		DFS(nrow, ncol, dir, count, moves + 1, cycles);
	}
}

테스트 7 번 런타임 에러

로직은 동일하지만, DFS 알고리즘을 재귀 대신 스택을 사용한 반복적인 방법으로 바꾸었다. 이렇게 함으로써 잠재적인 스택 오버플로우 문제를 피할 수 있다. 각 시작점에서 DFS를 실행하여 사이클을 찾고, 해당 사이클의 크기를 계산하여 리스트에 추가한다. 이후 리스트를 오름차순으로 정렬한 뒤, 정수 배열로 변환하여 반환

package LV2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class H86052 {
	// 상, 우, 하, 좌로 움직이는데 필요한 델타값
	int[] dr = {-1, 0, 1, 0}; // 상, 우, 하, 좌
	int[] dc = {0, 1, 0, -1}; // 상, 우, 하, 좌
	// 각 위치와 방향에 대한 방문 상태를 기록하는 배열
	int[][][] visited;
	// 각 위치와 방향에서의 이동 횟수를 저장하는 배열
	int[][][] moveCount;
	// 입력으로 받은 격자
	String[] grid;
	// 격자의 행과 열의 개수
	int n, m;

	// 위치와 방향, 그리고 이동 횟수 등을 표현하는 클래스
	class Point {
		int row, col, dir, count, moves;

		Point(int row, int col, int dir, int count, int moves) {
			this.row = row;
			this.col = col;
			this.dir = dir;
			this.count = count;
			this.moves = moves;
		}
	}

	public int[] solution(String[] grid) {
		this.grid = grid;
		n = grid.length;
		m = grid[0].length();
		visited = new int[n][m][4];
		moveCount = new int[n][m][4];
		List<Integer> cycles = new ArrayList<>();

		int count = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				for (int k = 0; k < 4; k++)
					// 만약 방문하지 않은 위치라면, DFS를 시작한다.
					if (visited[i][j][k] == 0) {
						Stack<Point> stack = new Stack<>();
						// 시작 위치를 스택에 넣는다.
						stack.push(new Point(i, j, k, ++count, 1));
						while (!stack.isEmpty()) {
							Point p = stack.pop();

							// 이미 방문한 위치라면, 사이클을 확인한다.
							if (visited[p.row][p.col][p.dir] != 0) {
								// 사이클이라면, 사이클의 길이를 저장한다.
								if (visited[p.row][p.col][p.dir] == p.count)
									cycles.add(p.moves - moveCount[p.row][p.col][p.dir]);
								continue;
							}

							// 방문하지 않았다면, 방문 표시를 하고 이동 횟수를 기록한다.
							visited[p.row][p.col][p.dir] = p.count;
							moveCount[p.row][p.col][p.dir] = p.moves;

							// 해당 위치가 L이나 R이라면, 방향을 바꾼다.
							if (grid[p.row].charAt(p.col) == 'L') p.dir = (p.dir + 3) % 4;
							else if (grid[p.row].charAt(p.col) == 'R') p.dir = (p.dir + 1) % 4;

							// 다음 위치를 계산하고, 범위를 벗어나지 않도록 조정한다.
							int nrow = (p.row + dr[p.dir] + n) % n;
							int ncol = (p.col + dc[p.dir] + m) % m;

							// 다음 위치를 스택에 넣는다.
							stack.push(new Point(nrow, ncol, p.dir, p.count, p.moves + 1));
						}
					}

		// 사이클의 길이를 오름차순으로 정렬한다.
		Collections.sort(cycles);
		// 리스트를 정수 배열로 변환하여 반환한다.
		return cycles.stream().mapToInt(i -> i).toArray();
	}
}