[프로그래머스 Lv. 2] 빛의 경로 사이클

문제

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

접근

1. visit[grid 길이][grid의 각 문자열 길이][4]를 만들어준다.

2. 방문하지 않은 곳에 대해 재귀함수를 실행

3. get_locations라는 함수를 통해 다음으로 갈 좌표와 방향을 구해준다. R이면 현재 방향에서 + 1, L이면 현재 방향에서 +3하고 4로 mod 연산을 취해준다.

   3-1. 현재 방향이 동쪽(d가 3)일 때 현재 grid의 값이 L이면 다음 방향은 북쪽(d가 2)이 된다.

   3-2. 다음에 갈 좌표가 grid의 밖에 나갈 경우 재조정해준다.

4. 다음에 갈 곳이이 이미 방문한 곳 (visit[ny][nx][nd] == True)면 Cycle, 파라미터에 있는 cnt를 answer에 추가해준다.

5. 오름차순으로 정렬해서 return

Code

import sys

sys.setrecursionlimit(10 ** 6)


def solution(grid):
    dx = [0, -1, 0, 1] # 남 서 북 동
    dy = [1, 0, -1, 0]

    def get_locations(y, x, d, value):
        ny, nx, nd = 0, 0, d
        if value == 'R':
            d = (d + 1) % 4
        elif value == 'L':
            d = (d + 3) % 4

        ny = dy[d] + y
        nx = dx[d] + x

	# grid 밖으로 나갈 시 좌표 재조정
        if ny < 0:
            ny = n - 1
        elif ny >= n:
            ny = 0

        if nx < 0:
            nx = m - 1
        elif nx >= m:
            nx = 0

        return ny, nx, d

    def check(y, x, d, cnt):
        visit[y][x][d] = True
        value = grid[y][x]

        ny, nx, nd = get_locations(y, x, d, value)

        if visit[ny][nx][nd]:
            answer.append(cnt)
            return

        check(ny, nx, nd, cnt + 1)

    answer = []
    n, m = len(grid), len(grid[0])
    visit = [[[False] * 4 for _ in range(m)] for __ in range(n)]

    for y in range(n):
        for x in range(m):
            for d in range(4):
                if not visit[y][x][d]:
                    check(y, x, d, 1)

    return sorted(answer)

    return answer

여담

완전탐색 문제라 Lv. 2로 정한 것 같은데 솔직히 Lv. 2보다 어려운 문제