LeetCode April Challenge 2021 Longest Increasing Path in a Matrix

*** Time limit exceeded 나왔음.....

하지만 여기서도 주의해야 할 것은 max 값을 0으로 지정해놓으면 안되고

matrix.length랑 matirx[0].length값 제대로 지정했는지 확인해야 한다.

*** 같은 time limit exceeded 이지만 좀 더 코드가 깔끔한 거 같다.

dfs를 다르게 구성하는 방법

​

***결국 맨 처음 생각한 대로 dp + dfs로 생각해야 하는 문제이다.

A common approach to improve DFS is through memorization.

​

원래의 방법을 가지고는 도저히 dp랑 연관 짓기가 어려워 코드를 바꿨다.

하지만, loop 대신 condition조건문으로 바꿔서 사용하면 더 빨라질 듯하다.

무조건 다시 풀어봐야 할 문제이다.

*** 다음으로는, 우선순위 큐를 활용해서 푼 코드가 있었는데 굉장히 흥미로운 아이디어이고 활용도가 높은 거 같다.

우선순위 큐는 높은 우선 순위의 요소를 먼저 꺼내서 처리하는 구조이다.

add나 offer로 집어넣고 poll로 꺼낼 수 있다.

​

일반적으로 PriorityQueue<Integer> maxPQ = new PriorityQueue<>();

이런 식으로 선언하면 우선순위도가 높은 것부터 꺼낼 수 있다. 즉, 우선순위가 1인 것이 제일 먼저 나옴

하지만 아래처럼 new PriorityQueue<>((a,b) -> b[2] - a[2] );

라고 하면 우선순위가 마지막인 것부터 나온다.

이것에 관해서는 long integers는 overflow 문제로 new PriorityQueue<>((x, y) -> Integer.compare(y, x)) 라고 하는 것이 좋고,

나아가서는 new PriorityQueue<>(Collections.reverseOrder()); 이 더 좋다고 한다.

하지만!!!! 이 문제의 경우, 배열을 집어넣을 것이기 때문에 배열에서 무슨 요소를 기준으로 우선순위를 정할 것인지를 지정해줄 필요가 있다.

그렇기에 Collections.reverseOrder()이 아니라 아래의 방식이나 new PriorityQueue<>((x,y) -> Integer.compare(y[2], x[2]))가

적절하다.

​