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

2025. 2. 25. 12:56·코딩테스트/Python
목차
  1. 🔗 Problem Link
  2. ❔Thinking
  3. 💻Solution
  4. 🗝️keypoint
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. 행과 열이 1과 500사이기 때문에 최악의 경우 250,000개의 좌표가 존재하지만, 한번 진행한 경로는 동일한 사이클을 만들기 때문에 진행할수록 확인할 경로는 줄어든다.
  2. 방향을 계속해서 전환하는 방법으로 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
  1. 🔗 Problem Link
  2. ❔Thinking
  3. 💻Solution
  4. 🗝️keypoint
'코딩테스트/Python' 카테고리의 다른 글
  • [LeetCode] 605. Can Place Flowers
  • [LeetCode] 1768. Merge Strings Alternately
  • [Baekjoon] 1655. 가운데를 말해요
  • [Programmers] Level 2. 당구 연습
swwho
swwho
일상을 데이터화하다
  • swwho
    하루한장
    swwho
  • 전체
    오늘
    어제
    • 분류 전체보기 (188)
      • ML_DL (39)
        • MUJAKJUNG (무작정 시리즈) (18)
        • 딥러닝 공부하기 (21)
      • 데이터사이언스 (1)
        • EDA (1)
        • 데이터과학을 위한 통계 (0)
      • 데이터엔지니어링 (2)
      • 논문리뷰 (2)
        • Computer Vision (2)
      • Python 활용하기 (12)
      • 코딩테스트 (127)
        • Python (109)
        • MySQL (14)
      • Git (3)
      • MySQL 활용하기 (0)
      • 일상 이야기 (1)
  • 블로그 메뉴

    • 홈
    • 태그
  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
swwho
[Programmers] Level 2. 빛의 경로 사이클
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.