백준 1162번 도로포장 JAVA

요구사항 정의

• 노드 1부터 N까지 최소값으로 가는 경로의 합 찾기
• 가는 도중에 도로를 포장하여 최대 K번 경로를 0으로 만들 수 있음

제약 조건

• T(걸리는 시간) < 10^6
• N < 10^4
• M < 5*10^4

풀이 방법

문제 읽자마자 `벽 뚫고 이동하기` 문제가 생각났고 풀이 방법은 생각보다 쉽게 구할 수 있었음

또한 경로의 합이 N*T이기 때문에 long 타입을 사용했음

→ 다익스트라 + DP

 

근데 제출 과정에서 이슈가 몇 가지 있었는데, 처음에는 메모리 초과가 나서 왜그런지 몰랐음 

• 시간 초과
• 메모리 초과

 

 

내가 객체로 만들기 귀찮아서 long[], int[]로 큐에 넣어서 메모리 초과가 나는 거였음

생각보다 배열이 잡아먹는 메모리 크기가 크다고 생각했다. 그래서 POJO로 변경했음

 

시간 초과 문제는 이미 최소값보다 큼에도 갱신하려고 시도했기 때문인데

다익스트라는 최소값으로 뽑기 때문에 이미 뽑았을 때  더 경로의 합이 큰 경우가 존재할 수 있다. 

이런 경우에는 더 진행되지않도록 바로 가지치기를 해줘야한다.

 

if(w > dist[n][k]) continue; // 이미 w보다 작은 값으로 갱신됐다면, 더 진행하지 않기

 

코드