[ 프로그래머스 ] 86052 빛의 경로 사이클

Link | 프로그래머스 86052번 문제 : 빛의 경로 사이클

📌 About

그래프 탐색 문제이다.

모든 격자를 탐색하며 방향을 잡고 사이클의 길이를 측정하면 된다.

이동 방향은 다음과 같다.

이를 배열로 나타나면 다음과 같다.

final int[][] move = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

각각의 사이클 탐색에 있어서 이동 방향 D를 TILT 방향에 따라 바꾼다.

바뀐 이동 방향 D에 맞게 다음 격자의 R과 C를 바꾼다.

이미 이동한 통로(격자와 격자 사이)가 나오면 이는 사이클이 생성된 것이다.

이를 바탕으로 해결하면 된다.

📌 Solution

Step 1. 필요한 자료구조를 정의한다.

int R, C;				// 전체 ROW와 COLUMN 길이
char[][] tilt;			// 각 격자의 회전 방향 S, L, R
boolean[][][] passed;	// 각 통로의 방문 여부

final int[][] move = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};	// 격자 위치 이동

R = grid.length;
C = grid[0].length();
passed = new boolean[R][C][4];
tilt = new char[R][C];
for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++) tilt[r][c] = grid[r].charAt(c);

Step 2. 미방문한 통로를 탐색한다.

List<Integer> counts = new ArrayList<>();
for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
        for (int d = 0; d < 4; d++)
            if (!passed[r][c][d]) counts.add(pass(r, c, d));

Step 3. 미방문한 통로를 시작으로 사이클을 찾는다.

// r은 격자의 row, c는 격자의 column, d는 이동 방향
private int pass(int r, int c, int d) {
    int count = 0;

    while (true) {
        if (passed[r][c][d]) break;						// 방문한 통로이면 종료
        count++;										// 통로 개수++
        passed[r][c][d] = true;							// 방문 기록

        if (tilt[r][c] == 'L') d = (d + 3) % 4;			// Left tilt일 경우
        else if (tilt[r][c] == 'R') d = (d + 1) % 4;	// Right tilt일 경우
        												// 직진이 무변화

        r = (r + move[d][0] + R) % R;					// 다음 격자 row 위치
        c = (c + move[d][1] + C) % C;					// 다음 격자 col 위치
    }

    return count;
}

Step 4. 통로 길이를 정렬하여 반환한다.

return counts.stream().mapToInt(Integer::intValue).sorted().toArray();

📌 Code

GitHub Repository

public class Solution {

    int R, C;
    char[][] tilt;
    boolean[][][] passed;

    final int[][] move = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int[] solution(String[] grid) {
        R = grid.length;
        C = grid[0].length();
        passed = new boolean[R][C][4];
        tilt = new char[R][C];
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) tilt[r][c] = grid[r].charAt(c);

        List<Integer> counts = new ArrayList<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                for (int d = 0; d < 4; d++)
                    if (!passed[r][c][d]) counts.add(pass(r, c, d));
        return counts.stream().mapToInt(Integer::intValue).sorted().toArray();
    }

    private int pass(int r, int c, int d) {
        int count = 0;

        while (true) {
            if (passed[r][c][d]) break;
            count++;
            passed[r][c][d] = true;

            if (tilt[r][c] == 'L') d = (d + 3) % 4;
            else if (tilt[r][c] == 'R') d = (d + 1) % 4;

            r = (r + move[d][0] + R) % R;
            c = (c + move[d][1] + C) % C;
        }

        return count;
    }
}