[PROGRAMMERS] 86052 : 빛의 경로 사이클

오다혜·2022년 4월 20일
0

오랜만에 정말 재밌게 푼 문제다. 😊

해당 문제의 주안점은 두 가지이다.

  • 'L', 'R' 일 때 회전 처리
  • 노드의 각 방향마다 방문처리 (dfs인 것 같긴 한데 확실치 않다)

마지막에 4, 5, 6, 7, 8 런타임에러를 발생시킨 재귀대신 while로 푼 코드도 올려놓았다.

❤️ 회전 처리

어떤 방향에서 해당 노드로 접근했냐에 따라서 회전 방향(다음 노드로 이동하는 방향)이 바뀌게 된다.

왼쪽에서 'L' 노드에 방문한 경우 : 위 방향으로 바뀜
오른쪽에서 'L' 노드에 방문한 경우 : 아래 방향으로 바뀜

물론 하나씩 하드 코딩을 해도 되긴 하지만... 그렇게 풀긴 너무 귀찮고 좋은 방법은 아래와 같이 mod(%)를 이용하는 것이다.

아래의 move 함수는 현재 위치(x, y)와 접근 방향(direction), 해당 노드의 종류(opt : L | R | S) 를 받아서 다음 위치(nx, ny)와 다음 접근 방향(direction)을 반환한다.

dx = [0, 1, 0, -1]  # 상 우 하 좌
dy = [-1, 0, 1, 0]


def move(x, y, direction, opt):
    if opt == 'L':
        direction = (direction - 1) % 4
    elif opt == 'R':
        direction = (direction + 1) % 4

    nx = (x + dx[direction]) % row
    ny = (y + dy[direction]) % column

    return nx, ny, direction

방향을 위쪽부터 시계방향으로 위(0), 오른쪽(1), 아래(2), 왼쪽(3)이라고 하면 현재 방향 +1은 오른쪽으로 회전, -1은 왼쪽으로 회전을 의미하게 된다.

이것만 잘 만들었으면 굳이 귀찮게 하드 코딩을 안 해도 되니 일단락 되었다고 볼 수 있다.

🧡 각 방향마다 방문 처리

이 문제는 노드를 방문처리하는게 아니고 노드의 상하좌우 네 방향을 모두 방문 처리해주어야 한다. 같은 노드를 방문했다고 해도 방향이 다르면 사이클이 아니기 때문이다. 문제에서 보여주는 예시 그림을 잘 살펴보면 동일한 노드를 동일한 방향으로 방문했을 때 사이클을 이룸을 알 수 있다.

따라서 방문 처리를 위해 각 노드의 네 방향만큼(4 x row x column)의 visited 배열을 만들어야 한다.

이후엔 각 노드의 네 방향마다 dfs를 돌려주면 된다.

def search(x, y, direction):
    visited[x][y][direction] = True
    nx, ny, direct = move(x, y, direction, grid[x][y])
    if visited[nx][ny][direct]:
        return 1
    else:
        return 1 + search(nx, ny, direct)


def solution(g):
    global grid
    global visited
    global row
    global column
    
    grid = g
    row = len(grid)
    column = len(grid[0])
    visited = [[[False] * 4 for _ in range(column)] for _ in range(row)]

    answer = []
    for i in range(row):
        for j in range(column):
            opt = grid[i][j]
            for k in range(4):
                if not visited[i][j][k]:
                    answer.append(search(i, j, k))
    
    answer.sort()
    
    return answer

💛 재귀

파이썬에서만 그런지 모르겠지만 이 문제.. 재귀가 너무 깊어서 파이썬으로 푸니 4, 5, 6, 7, 8 번이 모두 런타임 에러가 난다. 로직 문제인 줄 알았으나 재귀가 너무 깊어서 난 에러였다.

그래서 마지막으로 while로 바꿔주었더니 통과!

💚 전체 코드

dx = [0, 1, 0, -1]  # 상 우 하 좌
dy = [-1, 0, 1, 0]


def move(x, y, direction, opt):
    if opt == 'L':
        direction = (direction - 1) % 4
    elif opt == 'R':
        direction = (direction + 1) % 4

    nx = (x + dx[direction]) % row
    ny = (y + dy[direction]) % column

    return nx, ny, direction


def solution(grid):
    global row
    global column
    
    row = len(grid)
    column = len(grid[0])
    visited = [[[False] * 4 for _ in range(column)] for _ in range(row)]

    answer = []
    
    # dfs
    for i in range(row):
        for j in range(column):
            opt = grid[i][j]
            for k in range(4):
                if not visited[i][j][k]:
                    route = 0
                    x, y, direction = i, j, k
                    
                    while not visited[x][y][direction]:
                        route += 1
                        visited[x][y][direction] = True
                        x, y, direction = move(x, y, direction, grid[x][y])
                    
                    answer.append(route)
    
    answer.sort()
    
    return answer
profile
프론트엔드에 백엔드 한 스푼 🥄

0개의 댓글