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

박철현·2024년 8월 8일

목록 보기

78/80

문제

코드

import java.util.ArrayList;

class Solution {
	static int R, C;
	static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1}; // 아래, 왼, 위, 오른
	static boolean[][][] isVisited;

	public int[] solution(String[] grid) {
		ArrayList<Integer> answer = new ArrayList<Integer>();

		R = grid.length;
		C = grid[0].length();

		isVisited = new boolean[R][C][4];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				for (int d = 0; d < 4; d++) {
					if (!isVisited[i][j][d])
						answer.add(light(grid, i, j, d));
				}
			}
		}

		return answer.stream().sorted().mapToInt(i -> i).toArray();
	}

	private static int light(String[] grid, int r, int c, int d) {
		int cnt = 0; // 이동거리

		while (true) {
			if (isVisited[r][c][d])
				break;

			cnt++;    // 거리증가
			isVisited[r][c][d] = true; // 방문처리
            // System.out.printf("isVisited[%d][%d][%d] = true\n", r, c, d);
			
            // isVisited 배열 : 해당 위치에서 상/하/좌/우로 갔는지 여부
            // 해당 방향으로 먼저 가서 회전 시키기
			r = (r + dr[d] + R) % R;
			c = (c + dc[d] + C) % C;

			if (grid[r].charAt(c) == 'L')
				d = d == 0 ? 3 : d - 1; // 좌회전
			else if (grid[r].charAt(c) == 'R')
				d = d == 3 ? 0 : d + 1; // 우회전

		}

		return cnt;
	}
}

전체 로직

visited[][][] : 해당 위치에서 상/하/좌/우 방향으로 빛이 나아갔는지 여부를 나타냄
- ex)visited[0][0][0] => (0, 0)번째 칸에서 아래 방향으로 나아간적이 있는지 여부
빛이 이동하는 모든 순환 경우를 봐야하기에 방문 여부를 체크하여 한번에 이어지는 그룹화
그룹의 수를 수가 적은 순으로 정렬하여 반환
상세 풀이은 아래 출처 참조

다른 블로그와 다른점

다른 블로그 풀이 결과

뭐가 다른가?

방문 여부를 true로 바꾸는 부분에 printf로 찍어봤을 때 해당 체크한 부분이 말이 안된다고 생각했습니다.
- isVisted 배열은 해당 위치의 칸에서 어디로 빛이 이동했는지 여부를 나타내는 배열입니다.
- 이미지에서 체크한 상황을 그림으로 그리면
  - isVisited[0][0][0] = true 이건 참
    - 이것처럼 처음에 S에서 아래로 내려가는 것은 참
  - isVisited[1][0][0] = true 이건 말이 안됨
    - 아래로 내려가서 L을 만났으면 회전해서 R쪽으로 이동을 해야하는데 지금 아래쪽을 방문했다고 표시를 하고있다.
    - 근데 답이 도대체 왜 맞을까 이해를 하다가 어찌저찌 순환이 맞아 떨어지는 것 같다고 생각하고..(혹시 아시는분 댓글 부탁드립니다..)
    - 그래서 L 인지 R 인지 봐서 회전하는 것을 하기 전에 빛을 먼저 해당 위치로 변경하였습니다.
수정 후 코드 출력 : 빛을 먼저 이동을 시키고 회전을 시켜 문제 풀이가 좀 더 직관적으로 변경한 것 같습니다.
- 문제 예시 그림처럼 왼쪽으로 이동 성공