[ Lv 2 ] 빛의 경로 사이클

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

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

---

풀이 과정

---

• 이게 난이도 2는 아닌거 같음. 전혀 감을 못잡고있다가 힌트를 보고 풀었음..

1. 전체 경우의 수를 탐색함.

   • 각각의 격자에서 왼쪽, 아래, 오른쪽, 위 네개의 방향으로 시작해서 이미 방문한 격자를 만날때까지 탐색
   • 미리 방향 배열을 만들어 두어서 좌회전일땐 +1, 우회전일땐 -1 하도록 함.
   • 탐색할 때 격자를 몇개 이동했는지 저장해 둠.

2. 격자의 끝을 넘어갈 때, 반대쪽 방향으로 들어오는건 그냥 나머지 연산자로 구현함.

   • (-1) % n = n-1, (n+1) % n = 1 인걸 이용

3. 저장해 둔 탐색 결과를 오름차순으로 정렬하여 리턴

---

소스 코드

def goto(grid, visited, start):
    x, y, way = start
    direction = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    length = 0
    while True:
        if visited[x][y][way]:
            break

        visited[x][y][way] = True
        length += 1

        if grid[x][y] == 'S':
            pass
        elif grid[x][y] == 'L':
            way = (way + 1) % 4
        elif grid[x][y] == 'R':
            way = (way - 1) % 4

        x = (x + direction[way][0]) % len(grid)
        y = (y + direction[way][1]) % len(grid[0])

    return length

def solution(grid):
    answer = []
    visited = [[[False] * 4 for _ in range(len(grid[0]))] for __ in range(len(grid))]

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in range(4):
                if visited[i][j][k] == False:
                    answer.append(goto(grid, visited, [i, j, k]))

    answer.sort()
    return answer