📚 Lv2 - 빛의 경로 사이클

빛의 경로 사이클

이해

최근에 풀었던 문제 중에 가장 어려웠다.

🦑 왜?
문제 이해가 안되서
이해는 했지만, 어떻게 구현해야할지 감이 오지 않아서

✔️ 문제 이해 팁

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

ex) 예를 들어, 다음 그림은 격자 ["SL","LR"]에서 1행 1열에서 2행 1열 방향으로 빛을 쏠 경우, 해당 빛이 이동하는 경로 사이클을 표현한 것입니다.

SL
LR


S → L (사이 1, S는 직진) 시작!
L → R (사이 2, L은 왼쪽으로 회전)
R → L (사이 3, R은 오른쪽으로 회전)
L → S (사이 4, L은 왼쪽으로 회전)
S → L (사이 5, S는 직진)

~

L → S (사이 16, L은 왼쪽 회전)

이제 S는 상하좌우로 모두 지나갔다. (끝)

결국 시작점에 다시 도착했을 때 상하좌우로 들어오거나 나가는 방향이 적어도 한 번씩 통과했다면, 끝이 난 것이다.

✏️ 왼쪽, 오른쪽으로 회전할 때

0	3
1	2

일 때, 0에서 왼쪽으로 간다면 3, 0에서 오른쪽으로 간다면 1이라고 했을 때
L : (0 + 3) % 4, R : (0 + 1) % 4 와 같은 공식이 성립한다.

소스

def bfs(r,c,k,grid, field):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    cnt = 0
    row = len(grid)
    col = len(grid[0])
    
    while True:
        if field[r][c][k]:
            break
        
        field[r][c][k] = 1
        r = (r + dx[k])%row
        c = (c + dy[k])%col
        
        # 다음 번째 K 값
        # L : 왼쪽이므로 정반대방향이다. (k + 3) % 4
        # R : 오른쪽이므로 정방향이다. (k + 1) % 4
        # S : 앞으로 전진
        if grid[r][c] == 'R':
            k = (k + 1) % 4
        elif grid[r][c] == 'L':
            k = (k + 3) % 4
        cnt +=1
    return cnt
        

def solution(grid):
    answer = []
    row = len(grid)
    col = len(grid[0])
    # 행열 상하좌우
    field = [[[0, 0, 0, 0] for _ in range(col)] for _ in range(row)]
    
    # 행열 좌표의 상하좌우로 지나가지 않은 곳이 있는지 체크한다.
    for r in range(row):
        for c in range(col):
            for k in range(4):
                # 아직 방문하지 않은 곳이라면
                if not field[r][c][k]:
                    answer.append(bfs(r,c,k,grid, field))
    answer.sort()
    return answer

참고 : https://velog.io/@chamchi_i/%EB%B9%9B%EC%9D%98-%EA%B2%BD%EB%A1%9C-%EC%82%AC%EC%9D%B4%ED%81%B4-python