[프로그래머스] 코딩테스트 연습 - 빛의 경로 사이클 (Python)

코딩 테스트 연습 - 빛의 경로 사이클 [월간 코드 챌린지 시즌3]

코딩테스트 연습 - 빛의 경로 사이클

 

챌린지에 참가해서 풀 때 분명 로직은 맞다고 생각되는데 채점을 하면 0점이 나와서 프로그래머스에 나오면 반드시 풀겠다고 다짐했던 문제입니다ㅋㅋ.. 참가 당시 참 화가 났던 문제...

 

풀이

풀이를 간단히 정리해보면 다음과 같습니다.

1. visit을 저장할 3차원 배열생성

2. cycle 완전 탐색

 

문제가 겁을 주기는 하지만 문제를 잘 이해하고 접근한다면 어려울 것이 없습니다.

먼저 cycle은 본인의 경로를 반복하는 것입니다.

그리고 문제에서 주어진 grid는 좌표가 넘어가면 반대쪽으로 나오기 때문에 "정지"라는 개념이 없습니다.

\( \Rightarrow \) 어느 방향으로 빛을 발사해도 언제나 Cycle이 생긴다.

  

이것을 다르게 생각해본다면 "하나의 점에서 하나의 방향으로 쏜 빛은 오직 하나의 cycle에만 포함된다"라고 볼 수 있습니다. 

\( \Rightarrow \) 한번 방문한 점과 방향은 다시 볼 필요가 없다.

 

그럼 하나의 점에는 [상, 하, 좌, 우] 4개의 방향으로 빛이 들어올 수 있으니 x, y좌표를 저장할 2차원 배열에 [상, 하, 좌, 우]를 저장할 배열을 추가한 3차원 배열을 생성해서 visit으로 사용하면 문제를 쉽게 해결할 수 있는 것입니다.

 

 

Code

def new_coord(x, y, grid):
    xlen, ylen = len(grid)-1, len(grid[0])-1
    if x < 0:
        x = xlen
    elif x > xlen:
        x = 0
    if y < 0:
        y = ylen
    elif y > ylen:
        y = 0
    return x, y

def solution(grid):
    answer, queue = [], []
    grid_visit = [[[0,0,0,0] for not_use in line] for line in grid] # [상, 하, 좌, 우]
    for i, line in enumerate(grid):
        for j in range(len(line)):
            for step in range(4):
                if grid_visit[i][j][step] == 1:
                    continue
                queue = [(i, j, step, 0)]
                while queue:
                    x, y, d, s = queue.pop()
                    x, y = new_coord(x, y, grid)
                    if grid_visit[x][y][d] == 1:    # visit 확인
                        break
                    else:
                        grid_visit[x][y][d] = 1
                    if (d == 0 and grid[x][y] == "S") or (d == 2 and grid[x][y] == "L") or (d == 3 and grid[x][y] == "R"):
                        queue.append((x - 1, y, 0, s + 1))  # 다음경로 "상"
                    elif (d == 1 and grid[x][y] == "S") or (d == 3 and grid[x][y] == "L") or (d == 2 and grid[x][y] == "R"):
                        queue.append((x + 1, y, 1, s + 1))  # 다음경로 "하"
                    elif (d == 2 and grid[x][y] == "S") or (d == 1 and grid[x][y] == "L") or (d == 0 and grid[x][y] == "R"):
                        queue.append((x, y + 1, 2, s + 1))  # 다음경로 "좌"
                    elif (d == 3 and grid[x][y] == "S") or (d == 0 and grid[x][y] == "L") or (d == 1 and grid[x][y] == "R"):
                        queue.append((x, y - 1, 3, s + 1))  # 다음경로 "우"
                answer.append(s)
    return sorted(answer)

 

 

문제 설명

각 칸마다 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 해야 합니다.