프로그래머스_python_빛의 경로 사이클

문제

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

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

풀이

1. 모든 위치에서 상하좌우로 접근을 시도한다.

2.

(i, j) 에 →으로 빛이 접근하는 경우,

(i, j) 에 ←으로 빛이 접근하는 경우,

(i, j) 에 ↑으로 빛이 접근하는 경우,

(i, j) 에 ↓으로 빛이 접근하는 경우는

모든 경로를 통틀어 유일하므로, 중복체크를 하면서 탐색한다.

코드

def solution(grid):
    size_R, size_C = len(grid), len(grid[0])
    passed = [[list() for j in range(size_C)] for i in range(size_R)]
    
    # 탐색
    def travel(r, c, dr, dc, w) : 
        while (dr, dc) not in passed[r][c] : 
            passed[r][c].append((dr, dc))        
            new_r, new_c = (r+dr)%size_R, (c+dc)%size_C
            if grid[new_r][new_c] == "L" : dr, dc = -dc, dr
            elif grid[new_r][new_c] == "R" : dr, dc = dc, -dr
            r, c, w = new_r, new_c, w+1
        return w

    # 모든 위치에서 상하좌우로 접근 시도
    ans = list()
    for i in range(size_R) : 
        for j in range(size_C) : 
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)] : 
                if (dr, dc) not in passed[i][j] : 
                    ans.append(travel(i, j, dr, dc, 0))
    
    return sorted(ans)