[프로그래머스(Python/Java)] 빛의 경로 사이클

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

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

이 문제는 배열을 적절히 잘 사용할 수 있는지에 대한 구현 능력과 / 문제 조건에 대한 상황을 잘 이해했는지를 테스트하는 문제인 것 같습니다.

 

[1] 먼저 "배열을 적절히 잘 사용할 수 있는가?"는 빛이 범위 밖을 벗어났을 때와 어떤 지점에서 빛이 꺾일 때 어떻게 처리를 해줄 것인가에 대한 내용인데요.

 

아래 주석에 써놓은 것처럼 범위를 벗어나는 경로에 대해서는 '%' 연산(파이썬)이나 If문(자바)로 범위 안에 있는 위치로 매핑을 해주어야 합니다. 그리고 빛이 꺾일 때 방향의 처리같은 경우, 맨 처음에 네 방향을 시계 방향(혹은 반시계 방향)으로 설정하고 방향 인덱스를 +1, 혹은 -1을 해준 뒤 '%' 연산을 통해 범위 안의 방향으로 매핑을 해주면 됩니다. 

 

[2] 다음으로 문제 조건에 대한 이해입니다. 바로 "언제 싸이클이 형성되는가"인데요.

 

우선 각 지점에서 나가는 경로는 4개가 존재합니다. 각 지점으로 들어오는 경로는 인접한 지점에서 나가는 경로와 같은 것이라고 취급할 수 있기 때문에 무시해도 됩니다. 그러면 모든 지점에 대해 상하좌우 네 방향에 대한 visited 배열을 만들 수 있는데요. visited 배열은 해당 경로를 지나간 적이 있는지를 체크하는 배열입니다. 만약 해당 경로를 지나간 빛의 경로가 존재한다면, 그 경로를 다시 택하는 순간 똑같은 사이클을 형성할 수밖에 없습니다. 따라서 탐색을 시작하기도 전에 visited[i][j][k](i,j,k는 각각 행, 열, 방향)가 true라면 해당 경로는 기존에 싸이클을 형성했던 경로이고, 탐색을 하다가 visited[i][j][k](i,j,k는 각각 행, 열, 방향)가 true라면 지금까지 탐색한 경로가 빛의 경로 싸이클임을 알 수 있습니다.

 

이 부분의 말이 약간 복잡할 수 있는데, 아래 코드를 참고해주세요.

[풀이 - 파이썬]

dx, dy = [-1,0,1,0],[0,1,0,-1]
def lightRoute(grid, visited, i, j, k):
   r, c = len(grid), len(grid[0])
   route = 1
   # 나가는 경로 체크
   visited[i][j][k] = True
   # 처음 방문한 노드 (ni, nj) = 다음 지점이면서 범위를 벗어나는 경우를 고려한다.
   nx, ny = (i + dx[k]) % r, (j + dy[k]) % c
 
   # 이제부터 이미 방문한 경로를 만나면 끝
   while True:
       # 직진 = 현재 방향 그대로 유지
       if grid[nx][ny] == 'S': pass
       # 좌회전 = (현재 진행 방향 - 1) % 4
       elif grid[nx][ny] == 'L': k = (k-1) % 4  
       # 우회전 = (현재 진행 방향 + 1) % 4
       elif grid[nx][ny] == 'R': k = (k+1) % 4           
 
       # 방문하지 않은 경로라면 길이를 1 증가시키고 방향 전환
       if not visited[nx][ny][k]:
           route += 1
           visited[nx][ny][k] = True
           nx, ny = (nx + dx[k]) % r, (ny + dy[k]) % c
       else:
           return route
 
def solution(grid):
   answer = []
   r, c = len(grid), len(grid[0])
   # 모든 격자점을 시작점으로 네 방향으로 빛을 진행시켜본다.
   # 북동남서(시계방향)로 나가는 경로를 체크하는 리스트
   visited = [[[False] * 4 for _ in range(c)] for _ in range(r)]
   for i in range(r):
       for j in range(c):
           for k in range(4):
                # 해당 지점에서 나가는 경로는 무조건 같은 싸이클을 형성
                if visited[i][j][k]:continue
                answer.append(lightRoute(grid, visited, i, j, k))
   return sorted(answer)

 

[풀이 - 자바]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Solution {
    static int r,c;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    public static int lightRoute(String[] grid, boolean[][][] visited, int i, int j, int k){
        int route = 1; // 싸이클의 길이
        visited[i][j][k] = true; // 처음 지점의 나가는 경로 체크

        int nx = i + dx[k] < 0 ? r-1 : (i + dx[k]) % r;
        int ny = j + dy[k] < 0 ? c-1 : (j + dy[k]) % c;

        // 이제부터 이미 방문한 경로를 만나면 끝
        while(true){
            // 직진 = 현재 방향 그대로 유지
            // 좌회전 = (현재 진행 방향 - 1) % 4
            if(grid[nx].charAt(ny) == 'L') k = k-1 < 0 ? 3 : (k-1) % 4;
            // 우회전 = (현재 진행 방향 + 1) % 4
            else if(grid[nx].charAt(ny) == 'R') k = (k+1) % 4;

            if(!visited[nx][ny][k]){
                route++;
                visited[nx][ny][k] = true;
                nx = nx + dx[k] < 0 ? r-1 : (nx + dx[k]) % r;
                ny = ny + dy[k] < 0 ? c-1 : (ny + dy[k]) % c;

            }
            else{
                return route;
            }
        }
    }
    public int[] solution(String[] grid) {
List<Integer> routes = new ArrayList<>();
        r = grid.length;
        c = grid[0].length();

        // 모든 격자점을 시작점으로 네 방향으로 빛을 진행시켜본다.
        // 북동남서(시계방향)로 나가는 경로를 체크하는 리스트
        boolean[][][] visited = new boolean[r][c][4];
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                for(int k = 0; k < 4; k++){
                    if(!visited[i][j][k]){
                        routes.add(lightRoute(grid, visited, i, j, k));
                    }
                }
            }
        }
        Collections.sort(routes);
        int[] answer = new int[routes.size()];
        for(int i = 0; i < routes.size(); i++){
            answer[i] = routes.get(i);
        }
        return answer;
    }
}