[프로그래머스 level2] 빛의 경로 사이클

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

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

해결방안

• Graph

알고리즘

1. 전제 조건
   1. 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
   2. 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
   3. 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
2. 칸이 이동하는 방향과 방문여부를 알아야 함
3. 모든 경우를 방문해보면 됨
   1. 이미 방문했다면 종료
   2. 방문한 적이 없다면 방문하고 회전 방향 변경
4. 방향을 알기위해 3차원으로 구성된 방문정보를 표시하는 배열 생성
   1. 방향 => 0, 1, 2, 3 (시계방향)
      1. 왼 -> 오 (0, 1)
      2. 위 -> 아래 (1, 0)
      3. 오 -> 왼 (0, -1)
      4. 아래 -> 위 (-1, 0)
         *칸을 벗어났을 경우, 예외처리 필요

핵심 팁

• 그래프에 대한 이해
  • 회전하는 것에 대한 고민이 조금 필요했다. 오랜만에 그래프 문제를 풀려고 하니 잘 안풀렸다.
• 3차원 배열에 대한 이해
  • 3차원 배열을 구성하는데 있어서 헤매였다. 그로인해 시간을 많이 잡아먹게 되었다.
• 문제 자체는 그렇게 어려운 문제는 아닌데 2차원 배열에 익숙한 사람이라면 3차원 배열을 생각하기조차 쉽지 않고 처음 사용할때 당황 할 수 있다. 하지만 충분히 나올 법한 문제이니 숙지 해두는것이 좋을 것이다.
• 힌트 
  • https://prgms.tistory.com/101

월간 코드 챌린지 시즌3 9월 해설

 

Python

def solution(grid):
    answer = []
    dire = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    r_length = len(grid)
    c_length = len(grid[0])
    # 4방향을 알아야 함 => 구조를 보자면 [r][c][d]가 아닌 [d][r][c]로 구성됨 => 직관적인 표현을 위해서는 배열을 출력해보는것이 좋음
    visited = [[[False for _ in range(c_length)] for _ in range(r_length)] for _ in range(4)]
    # 이동하는 함수
    def move(r, c, d):
        # 그냥 현재 위치에서 방향으로 1만큼 이동
        return r_length - 1 if r + dire[d][0] < 0 else 0 if r + dire[d][0] == r_length else r + dire[d][0], c_length - 1 if c + dire[d][1] < 0 else 0 if c + dire[d][1] == c_length else c + dire[d][1]
    
    # 방향 전환 함수
    def rotate(s, d):
        # S 일 경우, 직진
        # R 일 경우, 오른쪽으로 90도 회전 => d+1
        # L 일 경우, 왼쪽으로 90도 회전 => d-1
        if s == "R":
            d = d + 1 if d < 3 else 0 
        elif s == "L":
            d = d - 1 if d > 0 else 3
        return d
    
    # 3방향으로 방문하면서 이미 방문했다면 종료, 방문 안했다면 카운트 늘려가며 방문
    for i in range(r_length):
        for j in range(c_length):
            for k in range(4):
                if not visited[k][i][j]:
                    d, r, c = k, i, j
                    cnt = 0
                    while not visited[d][r][c]:
                        cnt += 1
                        visited[d][r][c] = True
                        r, c = move(r, c, d)
                        d = rotate(grid[r][c], d)
                    answer.append(cnt)
    return sorted(answer)

print(solution(["SL","LR"]))
# [16]
print(solution(["S"]))
# [1,1,1,1]
print(solution(["R","R"]))
# [4,4]

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/TIL_Public