[JAVA] 프로그래머스 - 빛의 경로 사이클 - Lv2

문제 내용

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

코딩테스트 연습 - 빛의 경로 사이클

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

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

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

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

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

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

---

제한사항

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

---

문제 접근 방법

어떤 특별한 알고리즘을 활용해 푸는 문제는 아니고 배열을 어떤식으로 선언하고 빛을 쐈을때 빛을 꺾는 부분을 잘 생각해주면 되는 문제이다.

처음에 문제에 접근했을 때는 격자를 나타내줄 2차원배열과 어느방향으로 빛을 쐈는지 알려줄 1차원배열을 이용했는데 코드가 복잡해졌고 틀린 코드가 됐다. 그래서 다른 분의 블로그를 참고했다.

 

기본적으로 이문제에서 알고 가야하는 점은 어느 곳에서나 빛을 쏘던지간에 빛은 무조건 순환된다. 이때 순환된 빛의 사이클을 구해주면된다. 즉, 각 점마다 상하좌우 4방향으로 한번씩 빛을 쏘고 그렇게 순환하고 나온 빛의 사이클을 저장공간에 담아서 오름차순 정렬해주면 된다는 말이다. 그럼 아래 로직을 보자.

 

로직

1. 방문 배열과 상하좌우 배열 선언
   배열을 2차원 1차원으로 나누는게 아니라 3차원배열을 선언해서 행,열,빛을쏜 방향을 나타내주는 배열을 만들어준다.
   그리고 BFS를 풀때와 마찬가지로 상하좌우로 빛이 움직일 수 있도록 1차원 배열을 두개 만들어준다. 다만 이때는 빛을 쏘는 방향을 아래 왼쪽 위 오른쪽 순서로 쏘도록 설정해주는데 이유는 2번에서 방향전환을 계산할때 편하도록 하기 위해서이다. -> 즉, k가 0=아래, 1=왼쪽, 2=위, 3=오른쪽 이된다.
   
   
2. 좌회전과 우회전
   현재 점이 'L' 일때와 'R' 일때를 구분하여 빛을 어느 방향으로 꺾을건지 정해주는 코드가 필요하다.
   즉, k를 방향이라고 한다면 다음과 같은 코드로 방향을 정해줄 수 있다.
   좌회전 일경우 -> k = (k+3)%4
   우회전 일경우 -> k = (k+1)%4
3. 빛이 쏴지고 다음에 도착하는 행과 열 재할당
   빛이 만약 격자 바깥으로 넘어가면 다시 반대편 격자 바깥에서 되돌아오는 규칙이 있다.
   이를 고려하여 빛이 다음에 도착하는 점에대한 인덱스(행, 열)를 재할당 해줘야한다.
   참고로 직진의경우 즉, 점이 'S' 일때는 2번을 무시하고 바로 3번을 실행해주면 된다.
   행의 경우 -> r = (r+x[k]+R) % R
   열의 경우 -> c = (c+y[k]+C) % C

자세한 내용은 코드를 보자

---

풀이

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

public class Solution {
	static boolean[][][] check;//[행][열][방향]
	static int R,C; //행, 열
	static int[] x = {-1, 0, 1, 0}; //아래쪽, 위쪽
	static int[] y = {0, -1, 0, 1}; //오른쪽, 왼쪽 
    
	public static int[] solution(String[] grid) {
		ArrayList<Integer> ans = new ArrayList<Integer>();
		
		R = grid.length; //행
		C = grid[0].length(); //열
		
		check = new boolean[R][C][4];
		
		//모든 정점에서 4가지 방향으로 빛 쏘기
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				for(int k=0; k<4; k++) {
					if(!check[i][j][k]) {
						ans.add(cycle(grid,i,j,k));
					}
				}
			}
		}
		
		Collections.sort(ans);//사이클 정렬
		int[] answer = new int[ans.size()];
		for(int i=0; i<ans.size(); i++) {
			answer[i] = ans.get(i); //배열에 담기
			System.out.println(answer[i]);
		}
		return answer; //반환
	}
	
	public static int cycle(String[] grid, int r, int c, int k) {
		int cnt=0;
		
		while(true) {
			if(check[r][c][k]) break;//다시 되돌아와 졌다면 사이클 생성된거.
			
			cnt++;//한번반복 할때마다 빛의 경로 이동.
			check[r][c][k] = true;//빛을 쏜 정점 방문처리(방향포함)
			
			if(grid[r].charAt(c)=='L') {
				k = (k+3)%4; //좌회전
			}else if(grid[r].charAt(c)=='R') {
				k = (k+1)%4; //우회전
			}
			
			r = (r+x[k]+R) % R; //빛쏘고나서 도착한 행
			c = (c+y[k]+C) % C; //빛쏘고나서 도착한 열
		}
		
		return cnt;//만들어진 사이클 리턴
	}
}

---

마무리

로직을 떠올려도 그걸 구현하기에 쉽지 않은 문제였다.. 과연 시간을 더쓴다고 했을때 이렇게 구현해 낼수 있었을까 하는 생각이든다. 아직 갈길이 멀다.