ps | |
---|---|
링크 | programmers.co.kr/… |
출처 | 프로그래머스 |
문제 번호 | 86052 |
문제명 | 빛의 경로 사이클 |
레벨 | Level 2 |
분류 |
구현 |
시간복잡도 | O(nm) |
인풋사이즈 | n<=500, m<=500 |
사용한 언어 | Python |
해결날짜 | 2022/01/12 |
"""Solution code for "Programmers 86052. 빛의 경로 사이클".
- Problem link: https://programmers.co.kr/learn/courses/30/lessons/86052
- Solution link: http://www.teferi.net/ps/problems/programmers/86052
"""
import itertools
DELTAS = ((0, 1), (1, 0), (0, -1), (-1, 0))
def solution(grid):
answer = []
row_num, col_num = len(grid), len(grid[0])
is_visited = [[[False] * 4 for _ in grid[0]] for _ in grid]
for r in range(row_num):
for c in range(col_num):
cur_r, cur_c = r, c
for dir_id in range(4):
if is_visited[r][c][dir_id]:
continue
for i in itertools.count():
if is_visited[cur_r][cur_c][dir_id]:
answer.append(i)
break
is_visited[cur_r][cur_c][dir_id] = True
dr, dc = DELTAS[dir_id]
cur_r = (cur_r + dr) % row_num
cur_c = (cur_c + dc) % col_num
if grid[cur_r][cur_c] == 'L':
dir_id = (dir_id + 1) % 4
elif grid[cur_r][cur_c] == 'R':
dir_id = (dir_id - 1) % 4
return sorted(answer)