[프로그래머스/Level2] 빛의 경로 (JAVA)

📖 문제

프로그래머스

 

 

💡  풀이 방식

• 구현 

 

1. 방문 배열과 상하좌우 배열 선언

- 3차원 방문 배열  : (행, 열, 빛을 쏜 방향) 저장

- 상하좌우 배열      : [아래, 왼쪽, 위, 오른쪽] 순서로 저장 (방향 전환 쉽게 하기 위해)

 

 

2. 좌회전과 우회전

d = (d+3) % 4;	// 좌회전
d = (d+1) % 4;	// 우회전

 

 

3. 빛 쏘고 다음에 도착하는 점에 대한 행과 열 재할당

i = (i + dx[d] + r) % r;	// 행
j = (j + dy[d] + c) % c;	// 열

 

 

 

💥 유의사항

어느 곳에서 빛을 쏘든 간 빛은 무조건 순환되고, 이 때 순환된 빛의 사이클을 구하자.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {-1, 0, 1, 0};    // 아래-왼-위-오른쪽
    static int[] dy = {0, -1, 0, 1};
    
    static String[] grid;
    static int r, c;
    static boolean[][][] visited;   // 행, 열, 빛을 쏜 방향
    
    static List<Integer> ans = new ArrayList<>();
    
    public int[] solution(String[] grid) {
        this.grid = grid;
        
        r = grid.length;
        c = grid[0].length();
        visited = new boolean[r][c][4];
        
        // 모든 정점에서 4가지 방향으로 빛 쏘기
        for(int i = 0 ; i < r ; i++) {
            for(int j = 0 ; j < c ; j++) {
                for(int d = 0 ; d < 4 ; d++) {
                    if(!visited[i][j][d])
                        ans.add(light(i, j, d));
                }
            }
        }
        Collections.sort(ans);  // 사이클 오름차순 정렬
        
        int[] answer = new int[ans.size()];
        for(int i = 0 ; i < answer.length ; i++)
            answer[i] = ans.get(i);
        return answer;
    }
    
    private static int light(int i, int j, int d) {
        int cnt = 0;    // 만들어지는 사이클
        
        while(!visited[i][j][d]) {
            cnt++;                      // 한 번 반복할 때마다 빛의 경로 이동
            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] + r) % r;
            j = (j + dy[d] + c) % c;
        }
        
        return cnt;
    }
}

 

 

---

💦 어려웠던 점

- 4개 방향에 대한 방문 여부 확인

 

 

🧐 새로 알게 된 내용

- 4방향 처리는 3차원으로!

- 사이클이 겹치면 안되니까 방문 배열 사용하기!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

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