본문 바로가기

문돌이 존버/프로그래밍 스터디

(프로그래머스 연습 문제 풀이) 빛의 경로 사이클

반응형
문제 설명
각 칸마다 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'로 이루어져 있습니다.

입출력 예
grid             result
["SL","LR"]      [16]
["S"]           [1,1,1,1]
["R","R"]        [4,4]

입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
길이가 16인 사이클이 하나 존재하므로(다른 사이클은 없습니다.), [16]을 return 해야 합니다.

입출력 예 #2
주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.
4개의 사이클의 길이가 모두 1이므로, [1,1,1,1]을 return 해야 합니다.

입출력 예 #3
주어진 격자를 통해 만들 수 있는 사이클들은 다음 그림과 같습니다.
2개의 사이클의 길이가 모두 4이므로, [4,4]를 return 해야 합니다.
import sys
sys.setrecursionlimit(10 ** 6) # 재귀허용 깊이 추가

def out(x, y, d, grid, dic):
    # 방향에 따라 x, y 좌표를 업데이트
    nx = x + dic[d][0]
    ny = y + dic[d][1]
    
    if nx >= len(grid): # 아래쪽으로 넘어갈 때
        nx = 0
    elif nx < 0: # 위쪽으로 넘어갈 때
        nx = len(grid) - 1
    if ny >= len(grid[0]): # 오른쪽으로 넘어갈 때
        ny = 0
    elif ny < 0: # 왼쪽으로 넘어갈 때
        ny = len(grid[0]) - 1
    return nx, ny

def dfs(state, org, route, grid):
    # 방향: 아래쪽에서, 왼쪽에서, 위쪽에서, 오른쪽에서 빛이 들어옴
    dic = {0: [-1, 0], 1: [0, 1], 2: [1, 0], 3: [0, -1]}
    x = state[0]
    y = state[1]
    d = state[2]
    visited[d][x][y] = 1
    
    nx, ny = out(x, y, d, grid, dic) # 좌표 업데이트
    value = grid[nx][ny]
    
    # 어느 방향에서 온 것인지를 고려한 계산법
    # ex) 현재 value=R이고, 위쪽 노드에서 온 것(d=2)이라면 우회전 즉 d=3이 되어야 함
    if value == 'R':
        d = (d + 5) % 4
    elif value == 'L':
        d = (d + 7) % 4
    
    # 처음 노드와 비교해서 싸이클일 경우 answer에 싸이클 길이 추가
    if org[0] == nx and org[1] == ny and org[2] == d:
        answer.append(route)
        return
    if not visited[d][nx][ny]: # 방문하지 않는 노드가 있으면 dfs 재귀반복
        dfs([nx, ny, d], org, route + 1, grid)
        
def solution(grid):
    global answer, visited
    answer = []
    # visited = n(행 갯수) x m(열 갯수) x d(방향)
    visited = [[[0] * len(grid[0]) for _ in range(len(grid))] for _ in range(4)]
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for d in range(4): # 4가지 방향
                dfs([i, j, d], [i, j, d], 1, grid)
    return sorted(answer)

해당 문제는 기존의 DFS 혹은 BFS를 활용한 문제들보다 한층 복잡했다. 그 이유는 방향을 고려해야 했기 때문이다. 즉 기존의 visited, nx, ny 등에서 1차원 더 생각해야 하는 것이다. 이를 명확히 파악할 수 있는 예시는 두 번째인데, 단순 "S"라는 격자가 주어져도 답은 [1, 1, 1, 1]로 4개가 나온다. 그림을 보면 왼쪽, 오른쪽, 위쪽, 아래쪽 각각에서 해당 노드에 빛을 쏘는 것을 다 고려한 것이다.

따라서 엄밀히 말하면 처음 노드에서 순회를 하는 것이 아니라 그 전에 어디서 빛을 쏠 것이냐부터 생각해야 한다. 그렇기 때문에 solution 함수에서 보듯이 for 반복문을 3개 쓰고 마지막 for문은 각 방향에서 오는 경우를 따지는 것이다. visited의 경우도 3차원 array고 마지막 차원이 각 방향을 나타낸다.

이외에 좌표를 업데이트하는 방식만 주의하면 된다. 기본적인 DFS에서는 x, y 좌표가 0보다 작거나 len(좌표)과 같아지면 재귀반복을 그만두거나 다른 노드로 넘어갔는데, 여기선 그렇지 않다. 방향에 따라 같은 열의 다른 행의 처음 혹은 마지막, 같은 행의 다른 열의 처음 혹은 마지막으로 넘어간다(해당 부분은 위 그림을 참고하자).

마지막으로 가장 중요한 것은 아래 코드이다.

import sys
sys.setrecursionlimit(10 ** 6)

 파이썬에서 재귀반복을 사용할 때 최대허용 깊이 디폴트 값(=1000)이 낮다는 점을 처음 알았다. 따라서 이를 설정하지 않으면 에러 메시지도 단순히 "런타임 에러"로 나오기 때문에 해결할 수 없게 된다. 향후 코딩 테스트를 볼 때 반드시 추가해줘야겠다...

다른 모범 참고 코드도 다양한 듯 하다. 그러나 결국은 4가지 방향을 고려한다는 것, x, y 좌표가 0보다 작거나 길이를 초과할 때 다시 돌아온다는 큰 로직은 모두 동일했다.

참조
https://bladejun.tistory.com/165

 

728x90
반응형