문제
A*는 게임과 로봇 공학에서 쓰이는 대표적인 경로 탐색 알고리즘입니다. f = g + h가 작은 순서로 칸을 탐색하는데, g는 지금까지 지불한 비용이고 h는 남은 비용에 대한 휴리스틱 추정치입니다.
격자에는 각 칸의 비용이 들어 있습니다. 칸에 들어가면 그 칸의 값만큼 비용이 들고, 0은 들어갈 수 없는 벽입니다. start에서 출발하며 (이 칸의 비용은 내지 않습니다) 위, 아래, 왼쪽, 오른쪽으로 이동할 수 있습니다.
휴리스틱으로 맨해튼 거리 |row - goal_row| + |col - goal_col|를 사용하는 A*를 쓰세요. 지나갈 수 있는 모든 칸의 비용이 1 이상이므로 이 휴리스틱은 과대평가하지 않으며, A*는 최적의 답을 반환합니다.
a_star_cost(grid, start, goal)를 구현하세요.
입력
grid: 칸 비용 행렬 (0 = 벽).
start, goal: [row, col] 형태의 위치.
출력
goal에 도달하는 최소 총비용을 반환합니다. 도달할 수 없으면 (start나 goal이 벽인 경우 포함) -1을 반환합니다.
제약 조건
1 ≤ 행 수, 열 수 ≤ 100
0 ≤ 각 비용 ≤ 9
예시
입력:
goal = [2, 2]
grid = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
start = [0, 0]
예상 출력:
expected = 4입력:
std::vector<long long> goal = {2, 2};
std::vector<std::vector<long long>> grid = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
std::vector<long long> start = {0, 0};
예상 출력:
long long expected = 4;입력:
long[] goal = new long[] {2, 2};
long[][] grid = new long[][] {
new long[] {1, 1, 1},
new long[] {1, 0, 1},
new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
예상 출력:
long expected = 4;설명
가운데는 벽입니다. 오른쪽으로 두 번, 아래로 두 번 (또는 아래 다음 오른쪽) 가면 비용 1인 칸에 4번 들어가므로 합계는 4입니다.
입력:
goal = [0, 2]
grid = [
[1, 9, 1],
[1, 9, 1],
[1, 1, 1]
]
start = [0, 0]
예상 출력:
expected = 6입력:
std::vector<long long> goal = {0, 2};
std::vector<std::vector<long long>> grid = {
{1, 9, 1},
{1, 9, 1},
{1, 1, 1}
};
std::vector<long long> start = {0, 0};
예상 출력:
long long expected = 6;입력:
long[] goal = new long[] {0, 2};
long[][] grid = new long[][] {
new long[] {1, 9, 1},
new long[] {1, 9, 1},
new long[] {1, 1, 1}
};
long[] start = new long[] {0, 0};
예상 출력:
long expected = 6;설명
9를 곧장 지나가면 9 + 1 = 10이 듭니다. 아래로 내려가 맨 아래 행을 따라간 뒤 다시 올라가면 비용 1인 칸에 여섯 번 들어가므로 합계는 6입니다.
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.