728x90
반응형
🔗 Problem Link
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
❔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과 500사이기 때문에 최악의 경우 250,000개의 좌표가 존재하지만, 한번 진행한 경로는 동일한 사이클을 만들기 때문에 진행할수록 확인할 경로는 줄어든다.
- 방향을 계속해서 전환하는 방법으로 d = (d+1) % 4 혹은 d = (d-1) % 4를 활용할 수 있다.
'코딩테스트 > Python' 카테고리의 다른 글
[LeetCode] 605. Can Place Flowers (0) | 2025.03.18 |
---|---|
[LeetCode] 1768. Merge Strings Alternately (0) | 2025.02.26 |
[Baekjoon] 1655. 가운데를 말해요 (0) | 2025.02.25 |
[Programmers] Level 2. 당구 연습 (0) | 2025.02.19 |
[Baekjoon] 2225. 합분해 (0) | 2025.02.18 |