(프로그래머스) 빛의 경로 사이클

지니·2021년 11월 1일

level2 프로그래머스

알고리즘

목록 보기

30/33

문제

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

풀이

1. dx, dy 배열 정의

우선, 회전에 이용할 dx, dy 배열을 만들어줘야 한다. 단, 시계 방향으로 정해줘야 나중에 구현하기 편해진다. 본인은 다음과 같이 정의하였다.

// 상 우 하 좌
int[] dx = {0, 1, 0, -1};
int[] dy = {-1, 0, 1, 0};

2. 특정 위치, 특정 방향에 대한 visited 배열 정의

본인은 다음과 같이 3차원 배열로 정의해줬다.

boolean[][][] visited;

visited[x][y][z]
x,y의 위치에 z 방향으로 지나간 적이 있는가를 의미한다.

z = 0 -> 위
z = 1 -> 오른쪽
z = 2 -> 아래
z = 3 -> 왼쪽

...와 같이 정의해줬다.

3. 좌회전, 우회전 구현하기

위에서 정의한 dx, dy를 가지고 좌회전, 우회전을 구현한다. 단, 현재 가리키고 있는 인덱스에서 좌회전 및 우회전을 했을 때 배열 범위를 넘어가는 것에 대한 처리는 따로 필요하다.

if (map[y][x] == 'L') {
	pos = (pos == 0) ? 3 : pos - 1; // 좌회전
} else if (map[y][x] == 'R') {
    	pos = (pos + 1) % 4; // 우회전
}

다른 코드를 보니 좌회전을 (pos + 3) % 4와 같이 구현하는 방법도 보았는데, 신박한 것 같다.

4. 실제로 해당 방향으로 x좌표와 y좌표를 이동

원리는 3번에서 좌회전, 우회전 구현하는 것과 유사하다. 가독성은 좋지 않지만 본인은 저렇게 구현했다.

x = (x + dx[pos] >= 0) ? (x + dx[pos]) % map[0].length : map[0].length - 1;
y = (y + dy[pos] >= 0) ? (y + dy[pos]) % map.length : map.length - 1;

코드

import java.util.*;

class Solution {
    List<Integer> list = new ArrayList<>();
    char[][] map;
    boolean[][][] visited;
    
    // 상 우 하 좌
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
   
    
    // map 설정
    public void setMap(String[] grid) {      
        map = new char[grid.length][grid[0].length()];
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = grid[i].charAt(j);
            }
        }
    }
    
    public int[] solution(String[] grid) {
        setMap(grid); 
        
        int width = map[0].length;
        int height = map.length;
        visited = new boolean[height][width][4];
        
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                for (int k = 0; k < 4; k++) {
                    
                    if (visited[i][j][k]) {
                        continue;
                    }
                    
                    int cnt = 0;
                    int pos = k;
                    
                    // i, j가 start
                    visited[i][j][k] = true;
                    int x = j;
                    int y = i;
                    
                    cnt++;
                    while (true) {
                        if (map[y][x] == 'L') {
                            pos = (pos == 0) ? 3 : pos - 1;
                        } else if (map[y][x] == 'R') {
                            pos = (pos + 1) % 4;
                        }

                        x = (x + dx[pos] >= 0) ? (x + dx[pos]) % map[0].length : map[0].length - 1;
                        y = (y + dy[pos] >= 0) ? (y + dy[pos]) % map.length : map.length - 1;

                        if (visited[y][x][pos]) {
                            if (x == j && y == i) {
                                list.add(cnt);
                            }

                            break;
                        }

                        visited[y][x][pos] = true;
                        cnt++;
                    }
                } 
            }
        }
        
        
        
        int[] answer = new int[list.size()];
        
        for (int i = 0; i < answer.length; i++) {
            answer[i] = list.get(i);
        }
        
        Arrays.sort(answer);
        
        return answer;
    }
}