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

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

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

---

 문제 풀이

구현에 관한 문제이다.

빛이 이동하는 순환 경로를 따져야 하기 때문에 한번 지나간 길은 다시 갈 수 없다.

또, 각 칸마다 상하좌우로 이동하는 것을 모두 따져야 한다.

이게 문제 해결의 시작이다.

 

위의 2가지 조건을 모두 따지기 위해서 3차원 배열을 만들고

딕셔너리를 만들어 이동방향에 맞는 값을 대입해준다.

 

모두 따져야 하기 때문에 3중 반복문으로 시작한다.

확인하는 특정 칸(x, y)의 이동방향(d)을 방문한 적이 없다면 

이동 횟수를 세고 계속 칸과 이동방향을 바꿔 반복해서 따지면 된다.

 

칸은 지금 좌표(x, y)에서 이동방향(d)에 맞게 계산하는데,

끝을 넘어갈 경우에 반대쪽 끝으로 다시 돌아오기 때문에 좌표는 나머지 연산을 이용해 계산한다.

x = (x + directions[d][0]) % r
y = (y + directions[d][1]) % c

 

이동방향은 칸에 적힌 문자에 따라서 S는 그대로, L은 왼쪽으로, R은 오른쪽으로 이동방향을 바꾼다.

S는 그대로니 확인할 필요가 없지만 나머지 두 경우는 아이디어 하나만 있으면 쉽다.

왼쪽으로 방향이 바뀌는 경우는 순서가 무조건 Up → Left → Down → Right → Up 순서이고

오른쪽의 경우는 무조건 Up → Right → Down → Left 순서이다.

무조건 정해진 순서를 따르기 때문에 지금 현재 이동방향(d)의 순서를 확인해서 다음 순서로 넘기면 된다.

if grid[x][y] == 'L':
	idx = 'ULDR'.index(d)
	d = 'ULDR'[(idx+1)%4]
elif grid[x][y] == 'R':
	idx = 'URDL'.index(d)
	d = 'URDL'[(idx+1)%4]

 

반복이 끝나면 이동 횟수를 추가해주고 잘 정렬해서 리턴해주면 된다.

느낀 점

정말 절망적인 문제였다. 과연 이게 level 2가 맞는 걸까..?

어떻게 접근할 염두가 안 나서 힌트를 살짝 봤다. 3차원 배열...

아! 싶어서 어찌저찌 구현했는데 코드가 너무 맘에 든다

 코드

def solution(grid):
    answer = []
    r, c = len(grid), len(grid[0])
    board = [[[] for _ in range(c)] for _ in range(r)]
    directions = {'U':[1,0], 'R':[0,1], 'D':[-1,0], 'L':[0,-1]}
    
    for x in range(r):
        for y in range(c):
            for d in 'ULDR':
                move = 0
                while True:
                    if d in board[x][y]: break
                    board[x][y].append(d)
                    move += 1
                    
                    x = (x + directions[d][0]) % r
                    y = (y + directions[d][1]) % c
                    
                    if grid[x][y] == 'L':
                        idx = 'ULDR'.index(d)
                        d = 'ULDR'[0] if idx == 3 else 'ULDR'[idx+1]
                    elif grid[x][y] == 'R':
                        idx = 'URDL'.index(d)
                        d = 'URDL'[0] if idx == 3 else 'URDL'[idx+1]
                        
                if move > 0 : answer.append(move)
            
    return sorted(answer)