[S/W 문제해결 응용] 4일차 - 보급로

이 문제는 2차원 배열이 주어지고 각 칸마다 높이가 주어진다. 각 칸을 이동할 때 각 칸에 적힌 숫자만큼 머무를 때, 0,0에서 부터 N-1, N-1 칸으로 이동하는 가장 빠른 시간을 출력하는 문제입니다.

 

마지막 칸에 가장 빠르게 도착하기 위해서는 각 칸에 가장 빠르게 도착하는 시간을 알고 있어야 한다고 생각했습니다. 그렇기 때문에 각 칸에 가장 빠르게 도착한 시간을 저장할 수 있는 dp라는 배열을 N*N 크기로 선언을 해주었습니다.

이 후 각 칸에 방문하는 방법은 queue를 이용해 bfs로 각 칸을 탐색할 수 있도록 해주었습니다.

 

맨 처음에 0,0을 queue에 넣어줌으로써 bfs로 탐색할 수 있도록 해주었습니다.

x,y 칸에서 nx,ny로 이동할 경우 nx, ny칸이 방문하지 않은 칸이거나, (현재까지 x,y 칸으로 가장 빠르게 이동한 시간 + nx,ny칸에서 머물러야하는 시간)이 (현재까지 nx,ny칸으로 이동할 수 있는 가장 빠른 시간)보다 작을 경우 그러니까 x,y칸에서 nx,ny칸으로 이동하는 것이 더 빠른 경우 dp[nx][ny]값을 dp[x][y]+(nx,ny에서 머물러야하는 시간)로 바꾸어주는 것입니다.

 

queue를 통해 모든 칸을 탐색하고 queue에 원소가 남아있지 않게 되는 경우 dp[N-1][N-1]이 답이 됩니다.

 

 

이번 문제를 풀게 되었을 때, 처음에 방법이 생각나지 않아 고민이 되었습니다. 이 후 마지막 지점으로 가장 빠른 시간에 도착할 수 있으려면 각 칸에 도착하는 가장 빠른 시간을 알아야 된다는 생각을 하게 되었고, 이를 통해 각 칸으로 이동할 수 있는 가장 짧은 시간을 저장하고 이를 사용해야겠다는 생각을 하게 되었습니다.

항상 각 지점마다 어떤 장애요소가 있고 이를 통과하여 도착 지점으로 가장 빠르게 도착할 수 있는 방법을 찾는 문제에서 많이 헤매게 되는 것 같습니다. 앞으로도 이런 유형의 문제를 많이 접해봐야 될 것 같습니다.