빛의 경로 사이클 - 프로그래머스 lv.2

문제 링크

프로그래머스

풀이

def solution(grid):
    n, m = len(grid), len(grid[0])
    dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]  # 위, 오른쪽, 아래, 왼쪽
    dd = {"L": -1, "R": 1, "S": 0}  # 왼쪽, 오른쪽, 직진
    
    # 현재 방향과 SLR을 입력 받아 다음 방향 출력
    def next_direction(d, command):
        return (d + dd[command]) % 4
    
    # 현재 위치와 방향을 입력 받아 다음 위치 출력
    def next_position(x, y, d):
        return (x + dx[d]) % n, (y + dy[d]) % m
    
    # 방문 여부를 저장하는 3차원 리스트 (x, y, 상하좌우)
    visited = [[[False] * 4 for _ in range(m)] for _ in range(n)]

    cycles = [] # 사이클의 길이를 저장할 리스트
    for x in range(n):
        for y in range(m):
            for d in range(4):  # 모든 방향에 대해 탐색
                if not visited[x][y][d]:
                    nx, ny, nd = x, y, d
                    path = []   # 경로를 저장할 리스트
                    # 방문하지 않은 지점을 따라 이동
                    while not visited[nx][ny][nd]:
                        visited[nx][ny][nd] = True
                        path.append((nx, ny, nd))
                        nx, ny = next_position(nx, ny, nd)
                        nd = next_direction(nd, grid[nx][ny])
                    # 사이클이 시작되는 지점을 찾기
                    if (nx, ny, nd) in path:
                        cycle_start = path.index((nx, ny, nd))
                        cycles.append(len(path) - cycle_start)

    return sorted(cycles)