[프로그래머스] GPS (Java)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/1837?language=java 

코딩테스트 연습 - GPS

1. 주의할 점

- BFS/DFS로 시도하면 TLE 혹은 '틀렸습니다'라는 문구가 출력된다

- DP로 접근한다

 

2. 구현

- 단순하게 그래프 문제라고 생각하고 DFS/BFS로 접근했다가 TLE와 '틀렸습니다'의 연속..(다만 이때, 1개의 채점에 여러개의 TC가 존재하여 1개라도 TLE 또는 메모리초과 발생시 틀렸습니다로 나타난다는 사람들의 의견이 존재)

- DP로 접근하라는 힌트를 보고 DP[a][b] 배열을 설정(a번째 목적지로 b를 가게될 경우 수정한 최소 오류를 저장)

- Li[]를 통해 존재하는 경로를 저장. 추가적으로, 이동하지 않고 머무를 수도 있으므로 본인에게 돌아가는 간선도 추가

- 정답으로는 오류의 최소값을 구할 예정이르모 DP[][] 배열 값을 K의 최대값보다 큰 1001로 전부 초기화한다

- DP[0][시작점]을 0으로 초기화한다

- K-1번에 대해 For문을 수행하여 현 지점인 J에 도달이 가능할 경우 다음을 수행한다

- 현 지점 J에서 갈 수 있는 모든 경로 Next에 대해, J와 Next 사이에 경로 존재 여부에 따라 수정 횟수 NV를 0 또는 1로 설정한다

- DP[i+1][Next]의 값을 현 지점까지의 최소 오류 횟수인 DP[i][j]와 NV의 합과 비교하여 작은 값을 가지도록 한다

- 목적지까지 도달하지 못할 경우 -1을 출력한다

 

import java.util.*;
import java.io.*;

class Solution {
    
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        //초기화
        int dp[][] = new int[k][n+1];       //[a][b]: a번째 목적지에 b가 왔을 때 다른 최소 횟수
        List<Integer> li[] = new List[n+1];
        for(int i=1;i<=n;i++){
            li[i] = new ArrayList<>();
            li[i].add(i);
        }
        for(int i=0;i<m;i++){
            int a = edge_list[i][0];
            int b = edge_list[i][1];
            li[a].add(b);
            li[b].add(a);
        }
        for(int i=0;i<k;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=1001;
        dp[0][gps_log[0]]=0;
        
        for(int i=0;i<k-1;i++){
            for(int j=1;j<=n;j++){      //시작지점
                if(dp[i][j]==1001) continue;      //도달 불가
                for(int l=0;l<li[j].size();l++){    //다음 지점
                    int next = li[j].get(l);
                    int nv = 0;
                    if(gps_log[i+1]!=next) nv=1;
                    dp[i+1][next] = Math.min(dp[i+1][next],dp[i][j]+nv);
                }
            }
        }
        int answer = dp[k-1][gps_log[k-1]];
        return answer == 1001 ? -1 : answer;
    }
}