2022년 4월 22일 - 빛의 경로 사이클

원래 금요일에 했어야 했지만,,, 금요일 아침에 너무 피곤한 나머지 하지못했따...끄흑...

 

그래서 이제서야 금요일 치의 코딩테스트 복습을 시작한다.

이번 문제는 빛의 경로 사이클 문제이다. 순서대로라면 주차요금을 먼저해야하지만 그래도 익숙한 것이 손이 더 간다고 그래도 문제 푸는데에 오랫동안 시간을 들였던 문제인 빛의 경로 사이클 문제부터 다시 보는게 좋을 것 같다.

 

지금 다시 문제를 보고 드는 생각은 이 문제는 또 다시 공부를 해야할 것만 같다..^^

 

일단 문제의 링크는 아래와 같다.

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

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

위의 문제를 풀 때, 가장 중요했던 문제는 방향 개수의 이차원 배열을 만드는 것이다. 즉, 삼차원 배열을 이용하여 문제를 풀 수 있다는 것이다.  그리고 각 삼차원 배열에 접근하여 해당 배열이 채워져있으면 넘어가고 채워져 있지 않으면 그 부분부터 시작하는 사이클을 만들어야 한다. 따라서 코드의 기본적인 구조는 다음과 같아야 할 것이다.

// 3차원 배열 생성

for(int i = 0; i < grid.length; i++){
	for(int j = 0; j < grid[0].length(); j++){
    	for(int d = 0; d < 4; d++){
        	// 만약 3차원 배열의 내용이 채워져 있지 않다면,
        	// 사이클을 찾는 함수를 넣는다.
        }
    }
}

 

이제 위의 3차원 배열을 생성해보자 해당 배열을 지나갔는지 안지나갔는지 (사이클이므로 지나간 곳은 다시지나갈 수 없음. 지나가게된다면 똑같은 경로를 지나가게 된다.) 확인을 하기 쉽게 boolean 타입으로 선언하면 되겠다.

 

boolean[][][] isVisited = new boolean[grid.length][grid[0].length()][4];

for(int i = 0; i < grid.length; i++){
	for(int j = 0; j < grid[0].length(); j++){
    	for(int d = 0; d < 4; d++){
        	if(!isVisited)
            	light(grid,i,j,d);
        }
    }
}

그렇게 적용하면 위와 같이 될 것이다. 그러면 이제 light이라는 사이클을 찾아서 isVaild 배열을 채워주는 메소드를 만들어야 한다. 일단 그렇다면 위의 코드는 기존의 프로그래머스에서 제공하는 solution 함수내부에 들어가게 될 것이다. 그렇게 내용을 변경한다. 그리고 grid.length와 grid[0].length()는 지속적으로 사용하므로 전역변수로 선언하자.

 

class Solution{
	int R, C;
    boolean[][][] isVisited;

	public int[] solution(String[] grid){
    	R = grid.length;
        C = grid[0].length();
        for(int i = 0; i < R; i++){
			for(int j = 0; j < C; j++){
    			for(int d = 0; d < 4; d++){
        			if(!isVisited)
                    	light(grid, i, j, d);
        		}
    		}
		}
        
        return ;
    }
    
    public void light(String[] grid, int i, int j, int d){
    	
    }
}

이제 light의 내부를 채워야 한다. 그런데 light로 구한 사이클의 길이를 반환하는 문제이므로 light의 결과가 어딘가에 저장이되어야 한다. 따라서 light의 반환값은 void가 아닌 int이고 light의 반환 값을 arraylist에 저장하자. arraylist를 저장하기 위해서는 java.util 라이브러리를 가져와야 한다. 그리고 stream을 사용하여 리스트 속 내용을 Integer에서 int로 명시적 변환하고 array로 변환한다음 오름차순으로 정렬한다. boolean isVisited 배열도 솔루션 메소드에서 초기화 한다.

 

import java.util.*;

class Solution{
	int R, C;
    boolean[][][] isVisited;

	public int[] solution(String[] grid){
    	ArrayList<Integer> light_length = new ArrayList<>();
        
    	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)
                    	light_length.add(light(grid, i, j, d));
        		}
    		}
		}
        
        return light_length.stream().sorted().mapToInt(i -> i).toArray();
    }
    
    public void light(String[] grid, int i, int j, int d){
    	
    }
}

 

solution의 내부는 모두 채웠으니 light 메소드의 내부를 정말 채울 차례다. 순서대로 내부 순서를 적어보자.

 

public void light(String[] grid, int i, int j, int d){
    // 사이클의 길이를 재야할 변수가 필요하다.
    
    // 사이클을 진행 할 때, 해당 면이 비어있지 않으면 멈춘다.
    // 비어있다면 카운트를 세고 isVisited[][][]를 채운다.
    // 사이클을 진행하기 위해 R일 경우, L일 경우를 나눠서 계산한다.
    // 그리고 R일 경우와 L일 경우에 따라 다음 접근할 사이클의 위치를 정한다.
    // 위를 계속 반복한다.
    
    // 사이클의 길이를 반환한다.
}

내부 순서는 위와 같이 될 것이다. 그렇다면 코드로 작성해보자.

 

public void light(String[] grid, int i, int j, int d){
    int cnt = 0;
    
    while(true){
    	if(isVisited[i][j][d])
        	break;
        cnt++;
        isVisited[i][j][d] = true;
        if(grid[i].charAt(j) == 'L'){
        
        }
        else if(grid[i].charAt[j] == 'R'){
        
        }
        
    }
    
    return cnt;
}

위처럼 코드를 작성하면 될 것같다. 이제 if와 else문을 채워야하는데 이부분은 나도 아직 이해가 가지 않지만 일단 적어보겠다.

 

public void 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;
        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;
        }
        r = (r + dr[d]+R) % R;
        c = (c + dc[d]+C) % C;
    }
    
    return cnt;
}

내 생각대로 해보자면 왼쪽일 때 (grid[r].charAt(c) == 'L')는 좌회전을 하고 오른쪽일 때는 우회전을 하는 사이클이 그려진다. 따라서 좌회전일때는 d가 감소하는 쪽으로 (방향이 계속변화하므로), 우회전일때는 d가 증가하는 쪽으로 진행하기 때문에 이를 통해 d를 변화하는 것으로 볼 수 있다.

아래의 r과 c를 변화하는 것은 각 방향에 따라서 어디로 향하는지 dr과 dc에 적어둬서 방향에 따라 가야할 x, y 좌표를 찾기 위해 변화하는 것이라고 생각된다. 이때 R과 C를 더해주는 이유는 각 상황에따라서 마이너스가 나올 수도 있기 때문이다. 이를 R과 C를 넣어줌으로서 사전에 방지한다.

 

따라서 전체 코드는 아래와 같다.

 

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;

    static 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));
                }
            }
        }
        System.out.println(answer);
        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;

            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;

            r = (r + dr[d] + R) % R;
            c = (c + dc[d] + C) % C;
        }
        return cnt;
    }
}

 

이번주에 다시한번 코드를 재작성해보는 시간을 가져야겠다.