[프로그래머스 Level2] 빛의 경로 사이클 - 파이썬(Python) - 월간 코드 챌린지 시즌3

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

프로그래머스

문제 설명

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

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

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

이 격자에는 길이가 16인 사이클 1개가 있으며, 다른 사이클은 존재하지 않습니다.

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

 

 

 

---

처음에는 모든 칸마다 상하좌우를 탐색해보면서 사이클을 만들고, 그 사이클이 이미 존재한다면 무시하고 존재하지 않는다면 그 정보를 저장하는 방식으로 구현하려고 했다. 이렇게 되면 단점이 매우 복잡하고.. 굳이 탐색해보지 않아도 될 위치를 탐색하게 될 수 있다. 검색으로 3차원 배열이 도움이 된다는 힌트를 얻고 곰곰이 생각해보다 구현에 성공했다!

 

n을 grid의 행의 길이, m을 grid의 열의 길이라고 했을 때, dp[n][m][4]의 3차원 배열을 만들어 이용하였다.

3차원의 4의 크기는 각각 (상, 하, 좌, 우)를 의미한다.

사이클이 겹치지 않을 조건은 어떠한 위치에서의 상하좌우를 두 번 이상 지나지 않는 것이다.

 

"0=상, 1=하, 2=좌, 3=우"라고 했을 때, 격자의 칸에서 'S'가 확인된다면 방향은 변하지 않으며, 그 외에는 아래와 같이 변화됨을 확인했다.

L = {0:2, 1:3, 2:1, 3:0}
R = {0:3, 1:2, 2:0, 3:1}

 

 

따라서, 

1. 모든 칸들의 상하좌우를 시작점으로 탐색을 시도한다.
2. 경로 중, dp에 표시되어 있는 것이 있다면 취소된다.
3. y와 x 위치가 방향키에 의해 위치가 조정된다.
4. 모든 탐색이 마무리되면 answer에 사이클의 길이를 담는다.
5. answer를 오름차순하여 반환한다.

 

 

 

<< 최종 코드 >>

def move_yx(y, x, i, n, m):
    if i == 0:
        if y-1 < 0:
            return n-1, x
        return y-1, x
    elif i == 1:
        if y+1 == n:
            return 0, x
        return y+1, x
    elif i == 2:
        if x-1 < 0:
            return y, m-1
        return y, x-1
    if x+1 == m:
        return y, 0
    return y, x+1

def solution(grid):
    answer = []
    n, m = len(grid), len(grid[0])
    dp = [[[0, 0, 0, 0] for _ in range(m)] for _ in range(n)]
    L = {0:2, 1:3, 2:1, 3:0}
    R = {0:3, 1:2, 2:0, 3:1}

    for i in range(n):
        for j in range(m):
            for k in range(4):
                y, x, cnt = i, j, 0
                while True:
                    if dp[y][x][k] == 1:
                        break
                    dp[y][x][k] = 1
                    cnt += 1
                    y, x = move_yx(y, x, k, n, m)
                    if grid[y][x] == 'S':
                        k = k
                    elif grid[y][x] == 'L':
                        k = L[k]
                    elif grid[y][x] == 'R':
                        k = R[k]
                if cnt:
                    answer.append(cnt)

    return sorted(answer)