[JAVA] 프로그래머스 LEVEL3 GPS

https://school.programmers.co.kr/learn/courses/30/lessons/1837

프로그래머스

코딩테스트 연습 > 2017 카카오코드 본선 > GPS

 

난이도: LEVEL3

알고리즘 유형: DP(Dynamic Programming)

 

문제 풀이 

DP로 풀지 않고 그래프 탐색을 사용해서 풀면 

시간 초과가 발생한다. 

경우의 수가 너무 많다. 

 

먼저 2차원 그래프를 만든다.

int [][] map = new int [n+1][n+1];
        
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
        if(i == j) continue;
        map[i][j] = MAX;
    }
}

for(int i = 0; i < m; i++){
    int v1 = edge_list[i][0];
    int v2 = edge_list[i][1];
    map[v1][v2] = 0;
    map[v2][v1] = 0;
}

불가능한 경로를 기록하기 위해 먼저 MAX로 초기화 하였다. (MAX = Integer.MAX_VALUE)

정점 x → 정점 x 같이 같은 정점으로 이동은 가능하니 continue (0)

 

주어진 정점 정보 배열 edge_list를 돌면서 

양방향으로 기록 

 

정리하면 특정 정점 a 정점 b에 대해서 

map[a][b] = 0 이면 경로가 존재 map[a][b] = MAX 면 경로 존재 X 

 

DP 배열을 만든다.

int [][] DP = new int [n+1][k];
for(int i = 0; i <= n; i++){
    Arrays.fill(DP[i], MAX);
}

 

DP 배열 행은 각 정점을 의미하고 열은 택시 이동 경로 인덱스를 의미한다. 

배열을 만들고 전부 MAX로 채워준다. 

 

DP[i][j] 의미 

정점 i에 대해서 gps_log[j] 에 최대한 경로 오류를 적게 수정하여 이동을 기록 

MAX 같은 경우에는 이동 불가능한 상태를 의미 

 

시작 경로는 수정 불가능하다. 

그래서 시작 경로만 gps_log[0] 에 해당하는 정점만 0을 준다.

 DP[gps_log[0]][0] = 0;

 

DP 로직 시작 

for(int i = 1; i < k; i++){
    int cur = gps_log[i];
    for(int j = 1; j <= n; j++){ // 시작 
        if(DP[j][i-1] == MAX) continue; // 이전 경로까지 경우의 수가 없으면
        for(int l = 1; l <= n; l++){ // 도착 
            if(map[j][l] == MAX) continue; // 경로가 없으면 continue
            if(l == cur){ // 원래 경로 
                DP[l][i] = Math.min(DP[l][i], DP[j][i-1]);
            }
            else{ // 원래 경로가 아니라면 수정 
                DP[l][i] = Math.min(DP[l][i], DP[j][i-1] + 1);
            }
        }
    }
}

변수 cur은 이번 gps_log의 정점이다.

 

정점을 이중 for문을 돌면서 

DP 배열을 채운다.

j는 시작 정점을 의미 l은 도착 정점을 의미

시작 정점 j가 DP[j][i-1] 이전까지 경우의 수가 없었다면 continue

map[j][l] = max map에 기록된 경로가 없으면 continue

 

이제 2가지 케이스로 나눠진다. (수정 o / 수정 x)

map에 기록된 경로가 있지만 본래의 gps_log[i](cur)이 아니라면 수정을 의미한다. 

마지막 경로는 수정 불가능

return DP[gps_log[k-1]][k-1] == MAX ? -1 : DP[gps_log[k-1]][k-1];

정답 코드

import java.util.*;
class Solution {
    static final int MAX = Integer.MAX_VALUE;
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        int [][] map = new int [n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) continue;
                map[i][j] = MAX;
            }
        }
        for(int i = 0; i < m; i++){
            int v1 = edge_list[i][0];
            int v2 = edge_list[i][1];
            map[v1][v2] = 0;
            map[v2][v1] = 0;
        }
        int answer = 0;
        
        int [][] DP = new int [n+1][k];
        for(int i = 0; i <= n; i++){
            Arrays.fill(DP[i], MAX);
        }    
        
        DP[gps_log[0]][0] = 0;
        for(int i = 1; i < k; i++){
            int cur = gps_log[i];
            for(int j = 1; j <= n; j++){ // 시작 
                if(DP[j][i-1] == MAX) continue; // 이전 경로까지 경우의 수가 없으면
                for(int l = 1; l <= n; l++){ // 도착 
                    if(map[j][l] == MAX) continue; // 경로가 없으면 continue
                    if(l == cur){ // 원래 경로 
                        DP[l][i] = Math.min(DP[l][i], DP[j][i-1]);
                    }
                    else{ // 원래 경로가 아니라면 수정 
                        DP[l][i] = Math.min(DP[l][i], DP[j][i-1] + 1);
                    }
                }
            }
        }
        return DP[gps_log[k-1]][k-1] == MAX ? -1 : DP[gps_log[k-1]][k-1];
    }
}