22116 창영이와 퇴근[priority queue,Binary Search]

https://www.acmicpc.net/problem/22116

22116번: 창영이와 퇴근

1.접근

인접한 격자로 가려면 경사의 절댓값을 지날 수 있어야 한다. 두가지 풀이가 생각났다.

1.이진탐색

경사의 범위가 1 ≤ Ar,c ≤ 1,000,000,000 이므로 가능한 경사의 값을 이진탐색으로 찾아서 값을 찾아가며 (1,1)->(n,n)으로 DFS를 돌려서 찾는 방법.

2.우선순위 큐

가장 경사가 적은값들만 찾아가면서 n,n이 나올때까지 탐색으로 찾아들어가는 방법

2.풀이

1.이진탐색

DFS로 그래프를 순회하며 (1,1)->(n,n)을 찾아간다. 지정한 경사보다 낮은 경사값들만 찾아 들어가다가 n,n에 도착하지 못하고 스택이 없어진다면 이진탐색으로 탐색값을 바꿔준다. 성공했을시 경사를 낮춰보고 실패했을시 경사를 높인다.

 

2.우선순위 큐

항상 경사가 낮은곳 부터 탐색할 수 있다면 n,n에 도착했을 때 현재까지 만난 경사들 중 최고값이 정답이 된다.

x좌표,y좌표,(x,y좌표에 갈때 경사) 를 담은 객체를 만들어 우선순위 큐에 넣는다. 객체를 큐에서 뽑아내면서 n,n을 만날때까지 있었던 경사들중 최고값이 정답이 된다.

3.코드

1.이진탐색

2.우선순위 큐

4.배운점

문제를 보고 모든경로를 파악하는것이 시간이 많이 걸릴 것 같아서 BS로 DFS를 돌릴생각을 했었는데 사실 DFS도 비슷한 경로를 추적하기 때문에 이진탐색으로 그래프를 여러번 탐색하는 방식이 더 시간이 오래걸렸다.