[Level 2] 빛의 경로 사이클 - JAVA

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

프로그래머스

---

[문제 풀이]

 

1. grid의 각 정점이 4개의 방향 (상, 하, 좌, 우)로 들렸는지 여부를 저장하기 위해 3차원 boolean 배열을 선언한다

boolean[][][] visited

• 방향(d)의 순서는 반시계방향으로 선언했고, 시계 방향이나 반시계 방향처럼 쭉 이어지게 정해야 나중에 방향 전환 (R 또는 L)  계산 시에 편하다

 

2. 각 정점마다 들리지 않은 모든 방향에 대해 빛의 경로를 구해준다 -> light 함수

 

3. 각 정점의 방향 별로 방문 처리를 하면서 들리지 않은 방향으로 방문해본다

S : 방향 유지 (직진)

R : 우회전

L : 좌회전

if (grid[r].charAt(c) == 'L')
	d = (d + 3) % 4; // 좌회전
if (grid[r].charAt(c) == 'R')
	d = (d + 1) % 4; // 우회전

 

방향 전환을 하고 d의 방향으로 한 칸 이동한다

만약 위치가 배열 밖으로 벗어난다면 반대편으로 이동시켜준다

 

각 행과 열의 길이를 더한 후, 그 길이로 다시 나눈 나머지로 바꾸면 배열을 벗어나는 좌표에 대해 처리가 가능하다

 

이동하면서 거리를 증가시켰던 count를 answer에 추가한다

그리고 반환 전에 오름차순으로 정렬해서 반환하면 된다!

 

 

 

 

자바 코드)

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

class Solution {
    static boolean[][][] visited;
    static int row, col;
    static int[] dx = {-1, 0, 1, 0}; //아래-왼-위-오른
    static int[] dy = {0, -1, 0, 1};

    public int[] solution(String[] grid) {
        List<Integer> answer = new ArrayList<>();
        row = grid.length;
        col = grid[0].length();
        visited = new boolean[row][col][4];

        for(int i=0;i<row;i++) {
            for(int j=0;j<col;j++) {
                for(int d=0;d<4;d++) {
                    if(!visited[i][j][d]) {
                        answer.add(light(grid, i, j, d));
                    }
                }
            }
        }

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

    public int light(String[] grid, int i, int j, int d) {
        int count = 0;

        while(!visited[i][j][d]) {
            count++;
            visited[i][j][d] = true;

            if(grid[i].charAt(j) == 'L') {
                d = (d+3) % 4; //좌회전
            }
            if(grid[i].charAt(j) == 'R') {
                d = (d+1) % 4; //우회전
            }
            
            i = (i+dx[d]+row) % row;
            j = (j+dy[d]+col) % col;
        }
        return count;
    }
}

 

 

---

참고)

https://jisunshine.tistory.com/175

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