[BOJ C++] 11909 배열 탈출

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

11909번: 배열 탈출

 

 

문제 이해

2차원 배열이 주어지고 시작점에서 도착점까지 이동을 해야합니다. 이동의 오른쪽 혹은 아래로만 갈 수 있으며 이전칸에 있는 숫자보다 다음칸의 숫자가 크다면 이전칸이 더 커지도록 +1씩 올려줘야 한다. +1씩 올려주는 것을 최소로 하는 경로로 갔을 때 몇번 +1 했는지를 구하는 문제였습니다.

 

 

입출력 조건

시간제한은 2초였고 배열은 최대 2222x2222 까지였습니다.

 

 

풀이

pq를 사용하여 다익스트라와 비슷한 느낌으로 문제를 해결하였습니다. 여기서 놓쳤던 점은 굳이 넣지 않아도 되는 지점들을 중복적으로 넣어줘서 시간초과가 났었습니다. 이를 잘 배제해주는게 주요했던 것 같습니다.

 

 

에러 및 느낀 점

앞서 말했듯이 답에 문제는 없지만 쓸모없이 반복적으로 중복되는 값들을 계속 넣어줘서 시간초과가 났었습니다.

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/11909_%EB%B0%B0%EC%97%B4%20%ED%83%88%EC%B6%9C.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.