빛의 경로 사이클

• 각 노드들에 대해서 다음 노드들이 주어져있을때, 사이클을 모두 찾는 문제이다. 처음 노드를 시작점으로 해서 경로대로 따라가며 사이클을 찾고, 그 다음에는 아직 방문하지 않았던 노드를 골라서 그 노드를 시작점으로 하는 사이클을 찾고, 이것을 모든 노드를 방문할때까지 수행하면 된다.
• 기본적인 사이클 찾기 문제들에 비해 조금 신경써야 할것은, 좌표 한개를 상태로 하는 것이 아니라, (좌표, 방향)이 상태가 된다는 것. 그래서 노드의 갯수는 R*C*4 가 된다.
• 시간 복잡도는 노드의 갯수인 O(R*C*4) = O(R*C)

"""Solution code for "Programmers 86052. 빛의 경로 사이클".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/86052
- Solution link: http://www.teferi.net/ps/problems/programmers/86052
"""

import itertools

DELTAS = ((0, 1), (1, 0), (0, -1), (-1, 0))


def solution(grid):
    answer = []
    row_num, col_num = len(grid), len(grid[0])
    is_visited = [[[False] * 4 for _ in grid[0]] for _ in grid]
    for r in range(row_num):
        for c in range(col_num):
            cur_r, cur_c = r, c
            for dir_id in range(4):
                if is_visited[r][c][dir_id]:
                    continue
                for i in itertools.count():
                    if is_visited[cur_r][cur_c][dir_id]:
                        answer.append(i)
                        break
                    is_visited[cur_r][cur_c][dir_id] = True
                    dr, dc = DELTAS[dir_id]
                    cur_r = (cur_r + dr) % row_num
                    cur_c = (cur_c + dc) % col_num
                    if grid[cur_r][cur_c] == 'L':
                        dir_id = (dir_id + 1) % 4
                    elif grid[cur_r][cur_c] == 'R':
                        dir_id = (dir_id - 1) % 4

    return sorted(answer)