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

문제 링크

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

문제 설명

• 특정 방향으로 빛을 쐈을 때
  • S이면 직진, L이면 좌회전, R이면 우회전
• 넘어가면 반대쪽에서 돌아옴
• 가능한 사이클의 길이를 오름차순으로 리스트에 담아 리턴

풀이

• 각 좌표마다 4방향 경로 저장
• 모든 경로 탐색
• 방문한적 없으면 재귀 돌면서 방문 체크
  • 재귀
    • 좌표, 방향, 깊이를 매개변수로 넘김
    • 사이클이면 종료
    • 아니면 문자에 따라 방향바꿔 재귀
• 방문한적 있으면 continue

후기

• 그림이 복잡해서 경로를 어떻게 저장해야할지 잘 안 떠올랐다
• 구현은 생각보다 쉬웠다

코드

import sys
sys.setrecursionlimit(1000000)

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
w, h = 0, 0
used = []
grid = []
answer = []

def solution(gridd):
    global w, h, used, grid, answer
    
    grid = gridd
    
    answer = []
    
    h = len(grid)
    w = len(grid[0])
    
    used = [[[0]*4 for _ in range(w)] for _ in range(h)]
        
    for i in range(h):
        for j in range(w):
            # 위 오 아래 왼
            for k in range(4):
                if used[i][j][k]:
                    continue
                    
                # 돌아~
                go(i, j, k, 0)
    
    answer.sort()
    return answer


def go(cy, cx, d, count):
    global used, answer
    
    if used[cy][cx][d]:
        answer.append(count)
        return
    
    used[cy][cx][d] = 1
    
    ny = (cy + dy[d]) % h
    nx = (cx + dx[d]) % w
    
    # 어디로 쏠지
    if grid[ny][nx] == "S":
        go(ny, nx, d, count+1)
    if grid[ny][nx] == "L":
        go(ny, nx, (d-1) % 4, count+1)
    if grid[ny][nx] == "R":
        go(ny, nx, (d+1) % 4, count+1)