[Programmers] Level 2. 빛의 경로 사이클

🔗 Problem Link

프로그래머스

---

❔Thinking

• S, L, R로 이루어진 격자각 주어질 때, 빛이 조건을 따라 이동하는 경로 사이클의 길이를 오름차순으로 반환한다.
• S는 진행 방향 그대로, L과 R은 각각 왼쪽과 오른쪽으로 방향을 전환하여 이동한다.
• 빛의 경로 사이클은 빛이 해당 경로를 따라 이동하다가 다시 처음 이동으로 돌아오는것을 말한다.
• 격자의 끝에서는, 경로를 유지한 채 반대쪽 끝으로 다시 돌아간다. 

---

💻Solution

1. 초기 풀이 (class 작성)

class LightsCycle():
    def __init__(self, board:list):
        self.board = board
        self.N = len(board)
        self.M = len(board[0])
        self.cycle_lengths = []
        self.visited = {}
        self.direction = {0:(-1,0), 1:(0,1), 2:(1,0), 3:(0,-1)}
        for i in range(self.N):
            for j in range(self.M):
                self.visited[(i,j)] = set()
    
    def move(self, s_x:int, s_y:int, direct:int):
        cnt = 0
        r, c, d = s_x, s_y, direct
        
        while d not in self.visited[(r,c)]:
            self.visited[(r,c)].add(d)
            r, c = (r+self.direction[d][0]) % self.N, (c+self.direction[d][1]) % self.M
            if self.board[r][c] == 'R': d = (d+1) % 4
            elif self.board[r][c] == 'L': d = (d-1) % 4
            cnt += 1
            
        self.cycle_lengths.append(cnt)
        return
    
    def start(self):
        for i in range(self.N):
            for j in range(self.M):
                for d in range(4):
                    if d not in self.visited[(i,j)]:
                        self.move(i, j, d)
        
        
def solution(grid):
    lights = LightsCycle(grid)
    lights.start()
    answer = sorted(lights.cycle_lengths)
    return answer

 

2. 간단하게 작성한 풀이

def solution(grid):
    R, C = len(grid), len(grid[0])
    direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = [[[0,0,0,0] for _ in range(C)] for _ in range(R)]


    def solve(x:int, y:int, d:int):
        res = 0
        while not visited[x][y][d]:
            visited[x][y][d] = 1
            x, y = (x+direction[d][0]) % R, (y+direction[d][1]) % C
            if grid[x][y] == 'L': d = (d+1) % 4
            elif grid[x][y] == 'R': d = (d-1) % 4
            res += 1
        return res


    ans = []
    for i in range(R):
        for j in range(C):
            for k in range(4):
                if visited[i][j][k] == 0:
                    ans.append(solve(i, j, k))             
    return sorted(ans)

---

🗝️keypoint

1. 행과 열이 1과 500사이기 때문에 최악의 경우 250,000개의 좌표가 존재하지만, 한번 진행한 경로는 동일한 사이클을 만들기 때문에 진행할수록 확인할 경로는 줄어든다.
2. 방향을 계속해서 전환하는 방법으로 d = (d+1) % 4 혹은 d = (d-1) % 4를 활용할 수 있다.