6142 : 탐색 종합 2 (대회형)
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×N 크기의 격자 지도가 주어집니다. 각 칸에는 0~9 사이의 숫자 또는 연산자 '+', '-', '*' 가 적혀 있습니다.
시작점 (0,0)에서 출발하여 도착점 (N-1, N-1)까지 상하좌우로 이동하여 도달할 때, 거쳐간 칸들의 수식을 차례대로 계산합니다.
이동할 때는 항상 (숫자) -> (연산자) -> (숫자) 순서로만 이동할 수 있습니다. 수식 계산은 우선순위를 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 진행합니다. (예:
도달 시 얻을 수 있는 수식 계산 결과의 최댓값과, 그 때의 최소 이동 칸 수(시작점과 도착점 포함)를 구하십시오.
시작점 (0,0)에서 출발하여 도착점 (N-1, N-1)까지 상하좌우로 이동하여 도달할 때, 거쳐간 칸들의 수식을 차례대로 계산합니다.
이동할 때는 항상 (숫자) -> (연산자) -> (숫자) 순서로만 이동할 수 있습니다. 수식 계산은 우선순위를 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 진행합니다. (예:
3 + 5 * 2 = 16)도달 시 얻을 수 있는 수식 계산 결과의 최댓값과, 그 때의 최소 이동 칸 수(시작점과 도착점 포함)를 구하십시오.
입력 설명
첫째 줄에 격자 크기 N (3 ≤ N ≤ 15, N은 항상 홀수)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 격자의 정보가 공백 구분되어 주어집니다. (0,0)과 (N-1,N-1)은 항상 숫자입니다.
둘째 줄부터 N개의 줄에 걸쳐 격자의 정보가 공백 구분되어 주어집니다. (0,0)과 (N-1,N-1)은 항상 숫자입니다.
출력 설명
조건을 만족하면서 도달할 수 있는 수식 결과의 최댓값과 그 때의 최소 이동 칸 수를 공백 구분하여 출력합니다. 도달 불가 시 -1 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
3 + 5
* 2 -
1 * 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3.4748129814359E+19 101도움
Dijkstra 우선순위 큐(또는 BFS)를 활용하여 각 정점 도달 시의 수식 최댓값과 최단 거리를 관리하되, 이동 시 연산자 칸과 다음 숫자 칸을 묶어 2칸씩 전진하도록 설계하면 수식이 완성되는 경로만 깔끔하게 탐색할 수 있습니다.