[Programmers] Lv2 빛의 경로 사이클 Java

문제 출처

[프로그래머스 코딩 테스트 연습]

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

프로그래머스

 

문제 풀이

문제는 다음 단계로 풀 수 있다.

1. 방문
2. 방향 전환
3. 적용
4. 횟수 적용

 

방향 전환에 대해서 알아보자

아래와 같이 오른쪽으로 회전하는 벡터가 있다.

회전하는 벡터

이를 코드로 변환하면 다음과 같다.

public int[][] direction = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

여기서 +1 씩하면 오른쪽으로 전환이 된다.

반대로 -1 씩하면 왼쪽으로 전환이 된다.

즉 다음과 같이 변환이 될 수 있다.

if (type == 'R')
    d = (d + 1) % 4;
else if (type == 'L')
    d = (d + 3) % 4;

자료형 정하기

처음에는 각 사이클 별로 배열에 저장해야 하는 줄 알 았다.

즉 아래와 같이 겹치는 경로가 있는 줄 알 았다.

하지만 아래 같은 경우는 없고 겹치는 경우도 없다.

즉 하나의 자료형에 저장해도 된다.

그렇기 때문에 모든 경로를 저장하는 boolean 배열을 선언한다.

잘못 생각한 경우

여기서 조금더 생각해야 할 것은 다음 그림과 같이 각각의 격자에는 총 4가지 방향이 있다.

그렇기 때문에 3차원 boolean 배열을 선언한다.

3차원 boolean 배열의 크기는 grid 격자 x, y크기와 방향의 크기 만큼 저장한다.

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

격자마다 4가지 방향

 

방문 하기

우선 모든 격자와 모든 방향을 방문 해야 하므로 이렇게 for 문으로 전부 방문하게 한다. 이때 x, y, d는 시작 지점과 방향이라고 생각하면 된다.

for (int y = 0; y < grid.length; y++)
    for (int x = 0; x < grid[0].length(); x++)
        for (int d = 0; d < 4; d++)
            toPassArray(x, y, d);

이후 방문을 하면 된다.

하지만 방문을 하기전 일단 생각할게 있다.

우선 사이클이므로 1번이라도 사이클을 돌면 다음에 방문을 안해도 된다.

아래에 시작 위치만 다른 같은 사이클이 있다.

잘보면 왼쪽 3번과 오른쪽 1번은 같다.

왼쪽을 방문 했으면 왼쪽의 정보가 다 저장이 되므로 오른쪽의 1을 시작할때 방문했는지 확인하면 된다.

if (pass[y][x][d])
    return

이후 방문을 하면 되는데 방문이 끝나는 조건은 이전에 방문 했으면 끝난다.

문제의 단계를 나눴던 것 처럼 코드를 작성하면 된다.

이후 방문하지 않을 동안 다음과 같이 반복하면된다.

방문 → 변환 → 적용 → num 증가

xy를 계산하기 편하게 하기 위해 xy를 배열로 선언했다.

이는 나중에 방향과 xy의 index를 맞춰서 한꺼번에 계산이 가능하다.

max 또한 계산을 편하게 하기 위해 index를 맞춘다.

각 사이클의 값을 저장할 num도 만든다.

int[] xy = {x, y};
int[] max = {grid[0].length(), grid.length};
int num = 0;

위 단계를 방문하지 않는 것 만 반복하고 방문은 boolean 배열에 true로 추가해주면된다.

pass[xy[1]][xy[0]][d] = true;

 

방향 전환하기

변환 또한 grid에서 해당 xy를 가져 와서 회전을 하면 된다.

char type = grid[xy[1]].charAt(xy[0]);
if (type == 'R')
    d = (d + 1) % 4;
else if (type == 'L')
    d = (d + 3) % 4;

 

적용하기

이후 방향의 x 부분이 0이 아니라면 1또는 -1이 있다는 것이 y부분은 없다는 것이니 index를 가리키는 i를 0으로 만들어준다.

이후 xy를 방향에 만큼 더해주고 격자에서 벗어난 것은 맞게 조정해준다.

또한 num을 1을 더해준다.

int i = direction[d][0] != 0 ? 0 : 1;
xy[i] += direction[d][i];
if (xy[i] == -1)
    xy[i] = max[i] - 1;
else if (xy[i] == max[i])
    xy[i] = 0;

num++;

 

횟수 적용

반복문을 빠져 나가면 result에 num을 추가해준다.

// Solution 클래스 인스턴스 변수
public ArrayList<Integer> result = new ArrayList<>();

// toPassArray 끝부분 (반복문 빠져 나간 다음)
result.add(num);

위의 코드를 적용하면 다음과 같이 모든 사이클을 방문하고 길이를 저장하는 함수를 만들 수 있다.

public boolean[][][] pass;
public ArrayList<Integer> result = new ArrayList<>();
public String[] grid;
public int[][] direction = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

public void toPassArray(int x, int y, int d) {
    if (pass[y][x][d])
        return;

    int[] xy = {x, y};
    int[] max = {grid[0].length(), grid.length};
    int num = 0;

    while (!pass[xy[1]][xy[0]][d]) {
        pass[xy[1]][xy[0]][d] = true;
        char type = grid[xy[1]].charAt(xy[0]);

        if (type == 'R')
            d = (d + 1) % 4;
        else if (type == 'L')
            d = (d + 3) % 4;

        int i = direction[d][0] != 0 ? 0 : 1;
        xy[i] += direction[d][i];
        if (xy[i] == -1)
            xy[i] = max[i] - 1;
        else if (xy[i] == max[i])
            xy[i] = 0;

        num++;
    }
    result.add(num);
}

이후 만든 결과를 solution에서 int형으로 정렬된 형태로 변환 시키면 된다.

public int[] solution(String[] grid) {
    this.grid = grid;
    this.pass = new boolean[grid.length][grid[0].length()][4];

    for (int y = 0; y < grid.length; y++)
        for (int x = 0; x < grid[0].length(); x++)
            for (int d = 0; d < 4; d++)
                toPassArray(x, y, d);

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

 

소스 코드

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

    public boolean[][][] pass;
    public ArrayList<Integer> result = new ArrayList<>();
    public String[] grid;
    public int[][] direction = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

    public void toPassArray(int x, int y, int d) {
        if (pass[y][x][d])
            return;

        int[] xy = {x, y};
        int[] max = {grid[0].length(), grid.length};
        int num = 0;

        while (!pass[xy[1]][xy[0]][d]) {
            pass[xy[1]][xy[0]][d] = true;
            char type = grid[xy[1]].charAt(xy[0]);

            if (type == 'R')
                d = (d + 1) % 4;
            else if (type == 'L')
                d = (d + 3) % 4;

            int i = direction[d][0] != 0 ? 0 : 1;
            xy[i] += direction[d][i];
            if (xy[i] == -1)
                xy[i] = max[i] - 1;
            else if (xy[i] == max[i])
                xy[i] = 0;

            num++;
        }
        result.add(num);
    }

    public int[] solution(String[] grid) {
        this.grid = grid;
        this.pass = new boolean[grid.length][grid[0].length()][4];

        for (int y = 0; y < grid.length; y++)
            for (int x = 0; x < grid[0].length(); x++)
                for (int d = 0; d < 4; d++)
                    toPassArray(x, y, d);

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