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

빛의 경로 사이클

문제설명

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

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

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

제한사항

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

풀이

가능한 모든 경로와 방향을 시작으로 사이클을 탐색해야한다. 만약 이미 방문한 방향과 노드라면 탐색하지 않아도 된다. 어차피 같은 사이클이기 때문이다.

사이클이 안 만들어지는 경우도 있는 줄 착각했는데 그게 아니라 서로 다른 사이클만 구하면 되는 거였다.

DFS 재귀로 풀다가 복잡해서 프로그래머스 해설을 참고했다.

• 우선 방문 표시를 위해 각 좌표 별로 4 방향을 체크할 수 있도록 3차원 배열을 만든다.
  • visited[r] [c] [d] : (r, c)에서 d 방향으로 나간적 있는지
• 모든 노드와 방향에 대하여 방문한 적이 없다면 사이클을 탐색한다.
• 출발점으로 다시 돌아올 때 까지 탐색

함수들

• move: 모듈러 연산으로 좌표를 넘어가면 다시 첨으로 돌아오도록 함
• rotate: 다음 노드가 R, L일 경우 방향 회전

이렇게 짤 경우 (r,c,d) 를 각각 한 번씩만 방문하기 때문에 O(n^2)으로 해결된다.

그리고 마지막에 답 리턴할 때 오름차순 잊지 말기 !!!!!!!!!!!!

def move(r, c, d):
    global directions, n, m
    dx, dy = directions[d]
    return (r + dx) % n , (c + dy) % m
​
def rotate(d, node):
    if node == 'R':
        d = (d + 1) % 4
    elif node == 'L':
        d = (d - 1) % 4
    return d
​
def solution(grid):
    global n, m, answer, directions
    answer = []
    n, m = len(grid), len(grid[0])
    visited = [[[False for _ in range(4)] for _ in range(m)] for _ in range(n)]
    directions = [[1, 0], [0, -1], [-1, 0], [0, 1]] # D, L, U, R
    
​
    for r in range(n):
        for c in range(m):
            for d in range(4):
                if not visited[r][c][d]:
                    cx, cy, cd = r, c, d
                    cnt = 0
                    while not visited[cx][cy][cd]:
                        visited[cx][cy][cd] = True
                        cnt += 1
                        cx, cy = move(cx, cy, cd)
                        cd = rotate(cd, grid[cx][cy])
                    answer.append(cnt)
    return sorted(answer)

회전하는 부분 잘 기억해 둬야겠다.

방향을 쓸 때 가로, 세로 섞어서 만들어놔야 회전 계산하기 편하다.