[프로그래머스 Lv.2] 빛의 경로 사이클 - Python

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

POINT

사이클이 형성되는 경우

• 갔던 길을 다시 지나가야 할 때, 사이클이 완성된 것이다. → 즉, 지나간 길을 방문 처리 해야 한다.
• 서로 다른 사이클에서 동일한 방향으로 같은 길을 지나는 경우는 없다.

방향 바꾸기 & 격자를 벗어나 다시 되돌아오기

방향도 한 칸씩 회전하고, 격자도 한 칸씩 이동한다. → 둘 다 1씩 증가/감소시키되, 배열 크기로 나눠서 나머지를 구해주면 다시 처음으로 돌아온다.

# 방향 바꾸기
directions = ["상", "우", "하", "좌"]
index = 0

# 우회전 (시계 방향으로 돌기)
index = (index + 1) % len(directions)
# 좌회전 (시계 반대 방향으로 돌기)
index = (index - 1) % len(directions)

풀이

• 출발점이 정해져 있지 않다. (0, 0)부터 끝까지 모든 경우를 확인한다.
• visited 배열에 [row][col][direction]으로 방문 여부를 저장한다.

1. 지난 적 없는 길이면, 그 격자에서 출발한다.
2. 이동하기 전에 1.방문 처리 하고,  2.좌표 이동, 3.사이클 길이 증가, 4.방향 전환을 진행한다.
3. 2를 계속 반복하다가, 다음으로 이동할 길이 이미 visited이면 사이클이 만들어진 것이다.
4. 사이클 길이를 answer 리스트에 저장한다.
5. 반복을 중단하고, 다른 출발점으로 넘어간다.

def solution(grid):
    answer = []
    
    w, h = len(grid), len(grid[0])
    
    # 각 격자별 상, 우, 하, 좌
    visited = [[[False] * 4 for _ in range(h)] for _ in range(w)]
    
    # 상, 우, 하, 좌
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    for i in range(w):
        for j in range(h):
            for d in range(4):
                # 출발
                if visited[i][j][d] == False:
                    count = 0 # 사이클 길이
                    x, y = i, j # 현재 위치
                    direction = d # 현재 방향

                    while True:
                        # 방문 처리
                        visited[x][y][direction] = True
                        
                        # 이동
                        x = (x + dx[direction]) % w
                        y = (y + dy[direction]) % h
                        count += 1

                        # 방향 전환
                        if grid[x][y] == "R":
                            direction = (direction + 1) % 4
                        if grid[x][y] == "L":
                            direction = (direction - 1) % 4
                        
                        # 사이클이 만들어지면
                        if visited[x][y][direction] == True:
                            answer.append(count)
                            break
    
    return sorted(answer)

참고 (리스트 선언)

# 아래는 모두 같은 배열이다
visited1 = [[[False] * 4] * 2] * 3
visited2 = [[[False] * 4 for _ in range(2)] for _ in range(3)]
visited3 = [[[False for _ in range(4)] for _ in range(2)] for _ in range(3)]
visited4 = [[[False, False, False, False] for _ in range(2)] for _ in range(3)]

print(visited1)
print(visited2)
print(visited3)
print(visited4)