[프로그래머스] 경주로 건설 / 2020 카카오 인턴십 / python

처음에 생각한대로 잘 풀리지 않아서 카카오 해설을 참고했다.

처음 생각했던 풀이

• 상하좌우 bfs로 퍼져나간다.
• 현재 보고 있는 방향과 달라질 경우 방향을 바꾼다.
• 방문 처리는 (y좌표, x좌표, 코너의 수, 보고 있는 방향)을 key 값으로 하는 map을 사용했다.
• 범위를 벗어나거나, 벽이 있거나, 이미 방문한 곳이면 무시한다.
• 골인 지점에 도착한 경우의 수가 가지고 있는 직선 도로 개수와 코너의 개수를 사용하여 결과값을 최소값으로 갱신한다.

카카오 풀이를 슬~쩍 참고

• 방문 처리를 [세로 좌표 R][가로 좌표 C][코너 개수 K][바라보는 방향 D] 방식으로 했다.
  • 코너 K개를 만들면서 (R, C) 위치에 도착했고, D방향을 바라보고 있을 때의 최단 거리를 의미한다.
  • 처음에 4차원 배열을 각 차원마다 최대 길이에 맞게 math.inf로 초기화 해주자.
• 코너의 개수는 NxN의 필드에서 최대 N*N개까지 가능하다.
• 갓카오는 역시 나와는 다르게 상하좌우로 퍼져나가는 방식이 아니라 현재 바라보고 있는 방향에서 왼쪽이나 오른쪽으로 방향을 돌리거나 앞으로 이동하는 경우를 생각했다.
• 위의 방식으로 4차원 배열에 최단 거리를 쭉~ 저장한다.
• 이제 4차원 배열에서 골인 지점에 해당하는 부분의 코너 개수 부분을 돌면서 코너 개수 부분의 안에 있는 바라보는 방향마다의 최단 거리가 math.inf가 아닌 정수값이 존재하는 곳을 찾는다.([N-1][N-1][코너 개수 K][바라보는 방향 D] 요기 말한거)
• 해당 부분에서의 최소 값이 바로 최단 거리, 즉 직선 도로의 개수이고 해당 최소 값이 존재한 코너 개수 부분의 인덱스가 코너의 개수가 된다.
• 두 값을 이용해서 비용을 반환하자 ~!

from collections import deque
import math

WALL = 1
UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3
ROAD_COST = 100
CORNER_COST = 500


def solution(board):
    visited = [[[[math.inf, math.inf, math.inf, math.inf] for _ in range(len(board)**2)] for _ in range(len(board[0]))] for _ in range(len(board))]
    q = deque()
    q.append((0, 0, 0, 0, RIGHT))
    q.append((0, 0, 0, 0, DOWN))

    while q:
        now_y, now_x, road_count, corner_count, now_direction = q.popleft()

        next_directions = get_left_and_right_direction(now_direction)
        for next_direction in next_directions:
            if now_y == 0 and now_x == 0:
                continue
            if not can_move(board, visited, now_y, now_x, corner_count + 1, next_direction):
                continue
            visited[now_y][now_x][corner_count + 1][next_direction] = road_count
            q.append((now_y, now_x, road_count, corner_count + 1, next_direction))

        next_y, next_x = get_front_location(now_direction, now_y, now_x)
        if not can_move(board, visited, next_y, next_x, corner_count, now_direction):
            continue
        visited[next_y][next_x][corner_count][now_direction] = road_count + 1
        q.append((next_y, next_x, road_count + 1, corner_count, now_direction))

    answer = math.inf
    for corner_count, road_counts in enumerate(visited[len(board)-1][len(board)-1]):
        min_road_count = min(road_counts)
        if min_road_count != math.inf:
            answer = min(answer, CORNER_COST*corner_count + ROAD_COST*min_road_count)

    return answer


def can_move(board, visited, next_y, next_x, corner_count, direction):
    if is_out_of_range(board, next_y, next_x, corner_count) or board[next_y][next_x] == WALL:
        return False
    if visited[next_y][next_x][corner_count][direction] != math.inf:
        return False
    return True


def is_out_of_range(board, y, x, corner_count):
    return x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or corner_count >= len(board)**2


def get_left_and_right_direction(direction):
    if direction == UP:
        return [LEFT, RIGHT]
    elif direction == RIGHT:
        return [UP, DOWN]
    elif direction == DOWN:
        return [RIGHT, LEFT]
    else:
        return [DOWN, UP]


def get_front_location(direction, now_y, now_x):
    if direction == UP:
        return now_y-1, now_x
    elif direction == RIGHT:
        return now_y, now_x+1
    elif direction == DOWN:
        return now_y+1, now_x
    else:
        return now_y, now_x-1