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

문제 요약

각 칸에 S, L, R 중 하나가 적힌 격자가 있다.

빛은 각 칸의 문자에 따라 다음과 같이 이동한다.

S: 현재 방향으로 직진
L: 현재 방향을 기준으로 좌회전
R: 현재 방향을 기준으로 우회전

빛이 격자의 끝을 벗어나면 같은 행 또는 열의 반대편 끝으로 이동한다.

격자에서 만들 수 있는 모든 빛의 경로 사이클 길이를 구한 뒤 오름차순으로 정렬해 반환해야 한다.

핵심 아이디어

빛의 상태는 현재 위치만으로 결정되지 않는다.

같은 칸에 있더라도 어느 방향을 바라보고 있는지에 따라 다음 이동 경로가 달라진다.

따라서 하나의 상태를 다음 세 가지 정보로 표현해야 한다.

(현재 행, 현재 열, 현재 이동 방향)

각 셀에는 위, 오른쪽, 아래, 왼쪽의 네 방향으로 빛이 들어올 수 있다.

격자의 행 개수를 R, 열 개수를 C라고 하면 전체 상태의 개수는 다음과 같다.

R × C × 4

각 상태에서 다음 상태는 정확히 하나로 결정된다.

아직 방문하지 않은 상태에서 출발해 같은 상태를 다시 만날 때까지 이동하면 하나의 사이클을 찾을 수 있다.

방향 표현

네 방향을 다음과 같은 번호로 표현한다.

0: 위
1: 오른쪽
2: 아래
3: 왼쪽

각 방향의 행과 열 이동량은 다음과 같다.

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

방향 번호가 시계 방향으로 증가하도록 배치했기 때문에 좌회전과 우회전을 간단한 식으로 계산할 수 있다.

좌회전

direction = (direction - 1) % 4

예를 들어 오른쪽 방향인 1에서 좌회전하면 위쪽 방향인 0이 된다.

위쪽 방향인 0에서 좌회전하면 다음과 같다.

(0 - 1) % 4 = 3

따라서 왼쪽 방향인 3이 된다.

우회전

direction = (direction + 1) % 4

예를 들어 오른쪽 방향인 1에서 우회전하면 아래쪽 방향인 2가 된다.

왼쪽 방향인 3에서 우회전하면 다음과 같다.

(3 + 1) % 4 = 0

따라서 위쪽 방향인 0이 된다.

격자 끝 연결하기

빛이 격자의 범위를 벗어나면 반대쪽 끝으로 이동해야 한다.

나머지 연산을 사용하면 별도의 범위 조건문 없이 이를 구현할 수 있다.

next_row = (row + dr[direction]) % row_count
next_column = (column + dc[direction]) % column_count

예를 들어 행이 2개인 격자의 0번 행에서 위쪽으로 이동하면 다음과 같다.

(0 - 1) % 2 = 1

따라서 반대쪽 끝인 1번 행으로 이동한다.

마지막 행에서 아래쪽으로 이동하는 경우도 다음과 같다.

(1 + 1) % 2 = 0

첫 번째 행으로 다시 돌아간다.

방문 배열

각 셀과 방향의 조합을 별개의 상태로 관리한다.

visited = [
    [[False] * 4 for _ in range(column_count)]
    for _ in range(row_count)
]

다음 두 상태는 위치가 같더라도 서로 다른 상태다.

(0, 0, 위쪽)
(0, 0, 오른쪽)

따라서 방문 배열도 3차원으로 만들어야 한다.

풀이 과정

1. 모든 시작 상태 확인

모든 셀에서 네 방향을 각각 시작 상태로 확인한다.

for start_row in range(row_count):
    for start_column in range(column_count):
        for start_direction in range(4):

이미 방문한 상태라면 이전에 발견한 사이클에 포함되어 있으므로 다시 탐색하지 않는다.

if visited[start_row][start_column][start_direction]:
    continue

2. 현재 상태 방문 처리

아직 방문하지 않은 상태라면 방문 표시를 하고 사이클 길이를 1 증가시킨다.

visited[row][column][direction] = True
cycle_length += 1

3. 현재 칸에 따라 방향 변경

현재 칸이 L이면 좌회전하고, R이면 우회전한다.

if grid[row][column] == "L":
    direction = (direction - 1) % 4
elif grid[row][column] == "R":
    direction = (direction + 1) % 4

현재 칸이 S라면 방향을 변경하지 않는다.

4. 다음 칸으로 이동

변경된 방향을 이용해 다음 위치를 계산한다.

row = (row + dr[direction]) % row_count
column = (column + dc[direction]) % column_count

5. 방문한 상태를 만나면 종료

다음 상태가 이미 방문한 상태라면 현재 사이클 탐색을 종료한다.

while not visited[row][column][direction]:

반복문이 종료되면 계산한 사이클 길이를 결과 배열에 추가한다.

answer.append(cycle_length)

6. 오름차순 정렬

모든 상태를 확인한 뒤 사이클 길이를 오름차순으로 정렬한다.

answer.sort()

Python 코드

def solution(grid):
    row_count = len(grid)
    column_count = len(grid[0])

    # 위, 오른쪽, 아래, 왼쪽
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]

    visited = [
        [[False] * 4 for _ in range(column_count)]
        for _ in range(row_count)
    ]

    answer = []

    for start_row in range(row_count):
        for start_column in range(column_count):
            for start_direction in range(4):

                # 이미 다른 사이클에서 방문한 상태라면 건너뛴다.
                if visited[start_row][start_column][start_direction]:
                    continue

                row = start_row
                column = start_column
                direction = start_direction
                cycle_length = 0

                # 같은 상태를 다시 만날 때까지 이동한다.
                while not visited[row][column][direction]:
                    visited[row][column][direction] = True
                    cycle_length += 1

                    if grid[row][column] == "L":
                        direction = (direction - 1) % 4
                    elif grid[row][column] == "R":
                        direction = (direction + 1) % 4

                    row = (
                        row + dr[direction]
                    ) % row_count
                    column = (
                        column + dc[direction]
                    ) % column_count

                answer.append(cycle_length)

    answer.sort()

    return answer

코드 설명

방향 배열

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

같은 인덱스의 dr, dc를 함께 사용하면 각 방향으로 이동할 수 있다.

방향 0: dr=-1, dc=0  -> 위
방향 1: dr=0,  dc=1  -> 오른쪽
방향 2: dr=1,  dc=0  -> 아래
방향 3: dr=0,  dc=-1 -> 왼쪽

세 가지 상태 정보

visited[row][column][direction]

빛의 경로를 구분하려면 행과 열뿐 아니라 방향도 방문 상태에 포함해야 한다.

방향을 제외하고 셀만 방문 처리하면 같은 셀에 다른 방향으로 들어오는 별개의 경로를 놓치게 된다.

회전 후 이동

if grid[row][column] == "L":
    direction = (direction - 1) % 4
elif grid[row][column] == "R":
    direction = (direction + 1) % 4

빛은 현재 칸의 명령에 따라 방향을 먼저 변경한 뒤 다음 칸으로 이동한다.

따라서 방향 계산 후에 행과 열을 변경해야 한다.

사이클 길이

cycle_length += 1

하나의 (행, 열, 방향) 상태를 방문할 때마다 경로 길이를 1씩 증가시킨다.

이미 방문한 상태를 다시 만나면 이후의 이동도 이전과 완전히 같아지므로 하나의 사이클이 완성된다.

전역 방문 처리

한 사이클에서 확인한 상태는 다른 시작점에서 다시 탐색할 필요가 없다.

visited를 모든 탐색이 공유하도록 만들면 각 상태를 전체 과정에서 한 번만 방문할 수 있다.

예시

다음 격자를 살펴보자.

grid = ["SL", "LR"]

격자는 2행 2열이고 각 셀마다 네 방향이 존재한다.

따라서 전체 상태 수는 다음과 같다.

2 × 2 × 4 = 16

한 상태에서 시작해 이동하면 16개의 상태를 모두 지난 뒤 처음 상태로 돌아온다.

따라서 길이가 16인 사이클 하나가 만들어진다.

[16]

시간 복잡도

행의 수를 R, 열의 수를 C라고 하자.

전체 상태는 각 셀마다 네 방향이 있으므로 다음과 같다.

4 × R × C

각 상태는 전체 탐색에서 한 번만 방문한다.

O(R × C)

마지막에 사이클 길이 배열을 정렬하는 비용이 추가되지만, 사이클의 개수도 전체 상태 수를 넘지 않는다.

공간 복잡도

각 셀의 네 방향에 대한 방문 여부를 저장한다.

O(R × C)

정리

이 문제는 위치뿐 아니라 방향까지 포함한 상태를 탐색하는 시뮬레이션 문제다.

풀이 흐름은 다음과 같다.

빛의 상태를 (행, 열, 방향)으로 정의
각 셀의 네 방향을 시작점으로 확인
L과 R에 따라 방향 변경
나머지 연산으로 격자의 반대편 이동
방문한 상태를 다시 만날 때까지 길이 계산
모든 사이클 길이를 오름차순 정렬

같은 셀이라도 이동 방향이 다르면 서로 다른 상태라는 점과, 모든 상태를 전역 방문 배열로 관리하는 것이 핵심이다.