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

빛의 경로 사이클

Programmers

문제 설명

각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다.

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
• 당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.
격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ grid의 길이 ≤ 500

  1 ≤ grid의 각 문자열의 길이 ≤ 500
  grid의 모든 문자열의 길이는 서로 같습니다.
  grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.

작성 코드

def solution(grid):
    answer = []
    ans=0
    # 가로길이와 세로 길이 정하기
    width=len(grid[0])
    height=len(grid)
    # 방향변환을 dictionary로 표현
    direction={"R":1,"L":-1,"S":0}
    # 방향은 아래,왼쪽,위쪽,오른쪽 순으로 설정
    direc=[(1,0),(0,-1),(-1,0),(0,1)]
    # 방문을 집합으로 표현
    route=set()
    # 모든 루트를 저장해 둠.
    for i in range(4):
        for j in range(height):
            for k in range(width):
                route.add((j,k,i))
    x,y,d=0,0,0
    pre_route=(0,0,0) # 초기는 0,0에서 아래방향으로 설정
    route.remove((0,0,0)) # 첫 방향을 꺼내고, 
    while route: 
        # 초기 (0,0,0), pre_route가 없으면 순환이 끊어진 경우임.
        if not pre_route: 
            y,x,d=route.pop() 
            pre_route=(y,x,d) # 값 하나를 받아옴.(순환 판별이기에 순서는 상관 X)
        # 가야할 방향 설정 후 좌표를 구하는 데,
        ddy=y+direc[d][0]
        ddx=x+direc[d][1]
        if ddx<0: # x축이 0보다 작으면
            ddx+=width # x축 마지막 좌표로 이동
        if ddy<0: # y축이 0보다 작으면
            ddy+=height # y축 마지막 좌표로 이동
        if ddx>=width: # x축이 마지막 좌표보다 커지면
            ddx-=width # x축이 0으로 이동
        if ddy>=height: # y축이 마지막 좌표보다 커지면,
            ddy-=height # y축이 0으로 이동
        # 이 때 만난 좌표의 문자를 direction에 넣어 다음 방향 설정
        d=(d+direction[grid[ddy][ddx]])%4
        # 만약에 route에 없음 (이미 순환한 적이 있는 경우)
        if not (ddy,ddx,d) in route:
            pre_route=False #이전 루트를 없애버림
            answer.append(ans+1) # 정답에 하나를 추가하여, 순환이 끊어진 경우 표현
            ans=0 # 다시 순환을 하게 만듦
            continue
        # route에 있음 (방문한 적이 없음)
        route.remove((ddy,ddx,d)) # 방문해야할 곳에서 삭제하고
        y,x=ddy,ddx #현재 좌표를 이동하고,
        ans+=1 # 순환 개수 1을 더함
    if ans: # 전부 다 끝나고 탈출하였는데도, 마지막 ans가 있는 경우에는 
        answer.append(ans+1) # answer에다가 추가하고,
    answer.sort() # 정렬하여 정답도출
    return answer